Results 1 to 13 of 13

Thread: crypto crackme thought experiment

  1. #1
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491

    crypto crackme thought experiment

    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?

  2. #2
    Programmer Run Amock... Bengaly's Avatar
    Join Date
    Aug 2001
    Location
    Somewhere over the Rainbow
    Posts
    289
    Blog Entries
    1
    hi mike,
    check this post:

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

    it is quite long, funny & interesting.
    ttl.
    "knowledge is now free at last, everything should be free from now on, enjoy knowledge and life and never work for everybody else"

  3. #3
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    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?
    Last edited by mike; January 6th, 2003 at 22:11.

  4. #4
    r4g3
    Guest
    Originally posted by Bengaly
    it is quite long, funny & interesting.
    ttl.
    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...
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  5. #5
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    OK, 'nuff with that other thread. It's irrelevant.

  6. #6
    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

  7. #7
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    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" ?

  8. #8
    FoolFox
    Guest
    Hello,

    If we had one good license, we could break it instantly (how?);
    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 promise that I have read the FAQ and tried to use the Search to answer my question.

  9. #9
    : Code Injector : nikolatesla20's Avatar
    Join Date
    Apr 2002
    Location
    :ether:
    Posts
    815

    "educated" guesses..

    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

  10. #10
    fcjohn
    Guest
    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:
    Suppose the plaintext M is m bits long. For illustration purposes, when m=64 we obtain the following results:

    For any RSA public key <N,e>, given C=M^e mod N it is possible to recover M in the time it takes to compute 2*2^(m/2) modular exponentiations. The attack succeeds with probability 18%. The algorithm requires 2^(m/2)*m bits of memory.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  11. #11
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    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...
    Last edited by mike; January 7th, 2003 at 23:15.

  12. #12
    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

  13. #13
    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

Similar Threads

  1. crypto thought crackme #6
    By mike in forum Mini Project Area
    Replies: 18
    Last Post: May 29th, 2006, 00:40
  2. crypto thought crackme #5
    By mike in forum Mini Project Area
    Replies: 12
    Last Post: January 22nd, 2003, 17:52
  3. crypto thought crackme #4
    By mike in forum Mini Project Area
    Replies: 4
    Last Post: January 18th, 2003, 02:58
  4. crypto thought crackme #3
    By mike in forum Mini Project Area
    Replies: 7
    Last Post: January 15th, 2003, 15:32
  5. crypto thought crackme #2
    By mike in forum Mini Project Area
    Replies: 9
    Last Post: January 13th, 2003, 19:25

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •