This is a thought experiment to show that RSA protections can sometimes be broken even though they use big keys.

Consider this protection scheme: User enters name and serial number. Program computes 48-bit CRC then raises it to a large power mod n, a 2048-bit number. Finally, checks to see that the encrypted CRC matches a stored value.

We want to write a serial number generator--no modification of code.

If we had one good license, we could break it instantly (how?); what if we don't? Brute-forcing the 48-bit keyspace would take months on hundreds of computers. There's another way that has a good probability of working that only needs one computer with a few hundred megs of RAM and less than a day. What is it?

hi mike,
check this post:

http://board.win32asmcommunity.net/showthread.php?s=&threadid=5200&highlight=rsa

it is quite long, funny & interesting.
ttl.

I've seen that particular algorithm proposed several times on sci.crypt. I came up with it myself when I first read about RSA. It doesn't work.

Does anyone have the answer to the easy question from the first post: how to break it with a single good license?

it is very long. wa funny at the begining. interesting ? hell no. that .. ehm .. *** sch.jnn continues with his 'you are very close .. blah blah ..' to the very end. red first 5 pages, got bored, @ #15 he still gives the same bull* :\

in short he`s an asshole. no more, no less.
How could someone actually could seriously claim to solve smf as well studies as IFP What else than some stupid 'visual multiplication' was proposed there ? Nothing! hmmm ...

oh & btw i`ve discovered smf extremely kewl & leet: a vb app to do 2 incredibly marvelous thing:
1. it gives the phone number given ip (dial-up connection)
2. once having the phone # it unpax al of aspx-ected targets out there on the net & hax the victims pc doing the following: the crt is damaged by imprinting "SEX" on it`s surface & the user is bit hard by the mouse ...

that shit should look similar to any mathematician as mine to anyone of you...

for the last note: haven`t you ever thought of this 'sollution' as so far 'revealed' by our new genius ? once wasted a whole sheet of paper to realise it`s useless...

OK, 'nuff with that other thread. It's irrelevant.

Howdy,

If we had one good license then why not make
our own little proggy to do the work ?
I smell something in PERL ala Maurer.

Yes/no/maybe ?

Later, Woodmann

So you have one name and serial; it concatenates them, computes a 48-bit CRC of the result, encrypts it and compares the ciphertext to a stored one. What work, specifically, would you do in your "little proggy" ?

Hello,



wow...i'm not into crypto but you raise my interest...

Does it involve a kind of quick factorisation of the know licence ?

Regards
FoolFox

I will call this an "internet educated" guess since I am certainly not a math expert BY FAR.

Here's the only thing I can think of to add to the thread - you are calculating a 48 bit CRC from concatenated strings, and then encrypting it.

Well, first of all, if you have a encrypted comparison, you know what is has to turn out to be. And in my "guess" that means the CRC always has to be the same value or it won't work. Is this right? (I mean if you encrypt a different CRC value, I doubt you would get the same as the stored encrypted value, ever?) So now you need to figure out the CRC algo so you know how to combine the strings?


Just my thinking as of now..

-nt20

As far as my limited experience goes, you're exactly right, nikolatesla20. Only one CRC "plaintext" will produce the correct stored value "cyphertext."

I'm curious about mike's method of solving it without a license. Obviously, factoring the 2048-bit n is out. My guess would be to use the weakness of the short message, as mentioned here: http://crypto.stanford.edu/~dabo/abstracts/ElGamalattack.html

A few important lines from the paper:

Well done, you two. That's the whole of it. Only one CRC is right; the author calculates what serial number needs to go with a name. Since CRC is linear, you can do it instantly if you know what CRC you're trying to reach (for those of you who doubt it, try looking at the definition of CRC32 and find four bytes whose CRC is 0xDEADBEEF).

The trick is the short message. Many 48-bit numbers can be factored into two numbers less than 28 bits long. Calculate j^e for j=0 to 2^28, store 4 bytes of the result. Then for each one, divide m^e by j^e and see if the other factor is in your database. Chances are pretty good it'll be in there for one of them {up near 50%, actually; the 18% from the paper applies to calculating sqrt(# of plaintexts). If you calculate more--like we do here with 2^28 instead of 2^24-- then the success rate improves pretty fast}.

If people like this sort of thing, I can design a few more with similar flaws...

Hi,

I like it, I instantly fell for it

Caught me looking to hard at the encryption instead
stepping back and looking at everything.

I would like to see some more, it may just drag me
into the crypto world

Peace, Woodmann

I spotted the CRC flaw with a known license key, but hadn't a clue how to retrieve the CRC without a license.

Certainly gets my vote for more