Predicting the next Math.random() in Java

A while back a friend of mine hosted a programming competition where you were given 9 random numbers one at a time and you had to guess the rank (the sorted position amongst the 9) of each as they are coming in. The goal was to submit a strategy in Java that will maximize the number of these games won. The best solution can guess right about 3.3% of the time but I figured if he was going to let me execute arbitrary code I might as well cheat and guess correctly 100% of the time. So I set out to see if I can predict the rest of the numbers in the stream after seeing just one.

So I started digging through java.util.Random’s source and found that it is just a linear congruential generator which can be easily to cracked to obtain the original seed. The rest of this post will show how (if you just want to get the code, you can find it here).

Read rest of this post…

 

Solving CAPTCHAs on Project Euler

A couple weeks ago I started doing Project Euler problems. Unfortunately this was during their security breach so login was disabled so I couldn’t get credit for any of the problems I solved. Now that account functionality is restored, I want to resubmit my answers (about 60 of them) on my actual login. Since they have a 30 second rate limiting between answer submissions, it would’ve taken me half an hour to manually resubmit. This was a little too tedious and boring so I wanted to automate it. But they do have a CAPTCHA you need to fill out for each submission to prevent this…

Fortunately their CAPTCHAs are were really weak (EDIT: Project Euler made their CAPTCHAs significantly harder since this post): digits only, uniform font/font-size/font-color/background, well separated, unobstructed, etc. It seems like the only variation is that each digit is slightly rotated. Here are a few typical examples:

Writing a naive solver for these CAPTCHAs is pretty easy. The rest of this post will outline how (link to code is at the end).

Read rest of this post…