Decryption challenge

Discussion in 'privacy technology' started by berndroellgen, Sep 13, 2011.

Thread Status:
Not open for further replies.
  1. berndroellgen

    berndroellgen Registered Member

    Joined:
    Nov 5, 2010
    Posts:
    59
  2. LockBox

    LockBox Registered Member

    Joined:
    Nov 20, 2004
    Posts:
    2,275
    Location:
    Here, There and Everywhere
    These kind of challenges are marketing gimmicks and, frankly, silly.
     
  3. berndroellgen

    berndroellgen Registered Member

    Joined:
    Nov 5, 2010
    Posts:
    59
    Marketing gimmick: If the competition (AES) is the wholy grale and the cipher is additionally available for free, there is obviously no room for doing marketing.

    Although I doubt it, let's see if the participants of this thread show sufficient strength of character and put the usual disparagements aside.

    I make a claim that is pretty serious and I back it up with a real-life challenge. The entire source code is readily available for download. Everything is real.

    Background: Until 1999 it was illegal to export software utilizing cryptography with keys longer than 40 bit outside of the U.S. I remember web browsers and e-mail software with 40 bit SSL being used in offices worldwide. 40 bit keys are quite easy for professionals to break, so those 40 bit were a compromise.
    Please correct me if I'm wrong.

    So more than 10 years ago, DES, 3DES, Blowfish, AES, etc. reduced to 40 bit were known to be easy to break (56 bit DES was broken at that time with special chips that all operated in parallel).
    Every day it gets easier to confirm that ciphers reduced to 40 bit are easy to break - e.g. using my little code breaker tool, which is available as C++ source code for free for everybody. My computer, which wasn't all that expensive two years ago, is capable of trying 4.6 million possible keys per second. So it takes a few days (at maximum) to break any 40 bit AES key.

    Now I claim that it's pretty difficult to break a 36 bit key of a different cipher (of course). Taking into account that the average user uses short keys (6 or 7 characters at most), it is obviously a plus for an encryption algorithm to make attacks on short keys quite difficult. Pretty neat, isn't it?
     
  4. x942

    x942 Guest

    1) The majority of people are using TrueCrypt, PGP, or AxCrypt. These programs all generate a random 256 bit key and encrypt the volume/file(s) with that key and than the key with you password. This means you have to either bruteforce the 256 but key or the password; the latter is normally the weaker one.

    2) Any weak password can be brute forced. It doesn't matter how long the key is if you password is only 5 characters I can crack it in no time. (Unless you are using multiple rounds when hashing or encrypting as this would slow down the attack).

    3) Any program that uses your unhashed password as the key should be disregarded. These programs would basically require a 64 character password to meet the entropy requirements for a 256 bit key. Wouldn't that be annoying? Seriously if you are using a program that does this switch to something else. Anything that use ONLY your password and does no hashing to make it a 256 bit key is utterly useless as the key length is the same as the password size.

    Good post though :thumb:
     
  5. berndroellgen

    berndroellgen Registered Member

    Joined:
    Nov 5, 2010
    Posts:
    59
    Dear x942, you are 100% right.

    I do the hashing and the encryption part with a minimum number of rounds. The cipher is just somewhat bigger than usual. The internal state is enormous in size and key setup requires a hundred thousand times more operations than DES or AES or likewise.

    This here might be interesting for quite a number of people:
    Encryption technology that is made available to the public is always lightweight, memory requirement is ultra low and light-weight ciphers run fast on CPUs that would today typically control washing machines and likewise.

    It might be a good idea to harmonize key setup complexity and memory consumption with processor speed.

    These two (at the time phantastic) microprocessors have been conceived in the "DES era":
    MOS Technology 6502, 8 bit, introduced in 1975: 0.5 MIPS at 1 MHz
    Motorola 68000, 16 bit, introduced in 1979: 1 MIPS at 8 MHz

    One of the requirements for all AES candidates was the compatibility with microcontrollers like the 8051 (1 MIPS at 12MHz) that can be found in cheap smart cards. This, on the other hand, neglects the fact that the Intel Pentium Pro, introduced in 1996 already delivered 541 MIPS at 200 MHz.
    In 2001, when AES was finally approved, the AMD Athlon processor already featured a staggering 3,561 MIPS at 1.2 GHz !

    And this is where we are today:
    Intel Core i7 Extreme Edition 990x, 64 bit, introduced in 2010: 159,000 MIPS at 3.46 GHz
    This chip runs 159000 times faster in comparison with technology from 1975 !

    And then there are GPUs with lots of processor cores running in parallel, outperforming universal processor chips by factor 100 or 1000 or whatever:
    http://www.geek.com/articles/news/r...for-2-10-with-amazons-cloud-service-20101122/

    The hash/cipher combination that I'm using for the geocaching challenge requires somewhat around 100000 times more operations than SHA-1/AES128 and more than a million times of the RAM capacity to effectively prevent attackers from mounting a distributed attack on GPU chips.
    It thus should be pretty difficult to break the code, although 36 bit are clearly very weak - for any cipher.

    It's a long post, but the message is pretty important: The stuff that is made available to the public matches technology from 1975 (5µm metal gate CMOS, megahertz transit frequency, CISC) and in order to match today's technology (32nm CMOS in combination with huge die sizes,100 gigahertz transit frequency, parallel pipelined RISC with multi-stage cache), there is the sheer need to scale the size of state-of-the-art ciphers up quite heavily. That's somehow pretty philosopical... and logical.
     
  6. x942

    x942 Guest

    I see what you mean. But I don't think we have to worry as much (provided you are using a strong password; which in this case it's not a strong one), as currently even the fastest super computers cannot crack anything longer than ~16 Characters in length in a reasonable amount of time. a 256 bit Symmetric key is still uncrackable with modern technology and would take longer than it took the big bang until now to crack the key.

    But passwords are always that weak point, if you created the same thing but used a 256 bit key instead of a 36 bit key (and provided there were no flaws in the algorithm) it would (at least in theory) be stronger than AES 256 bit just as it is stronger than 36 bit. Bruce Schneier also says we should increase rounds on 256 bit to add protection from those recent "paper based" attacks. (personally I am not sure why he also recommends 128 bit over 256 bit as those attacks aren't even possible IRL).
     
  7. Warlockz

    Warlockz Registered Member

    Joined:
    Oct 30, 2008
    Posts:
    642
    Last edited: Sep 15, 2011
  8. berndroellgen

    berndroellgen Registered Member

    Joined:
    Nov 5, 2010
    Posts:
    59
    Without a doubt, long passwords are a must.

    This forum is funny. At minimum one alias name appears to make sense.

    Back to general cipher-related ideas that are probably worth to be mentioned:
    Another question arises when block sizes increase (which they constantly do since decades): PPPoE and other widely-used network protocols only support short packet sizes. An MTU size of 1492 bytes is typical (as far as I remember).
    The larger the block size of a cipher, the more padding is required. This "sucks". The only cost-effective solution is a very small block size or a variable block size. The latter is especially desirable as this irradicates the need for extra measures like CBC mode.The video that shows my geocache and the GPS coordinates of that location has been encrypted with a 6-character long password. I've encrypted the entire 197 megabytes in a single block. So each bit in the ciphertext depends on each plaintext bit and on each bit of the password. That's pretty cool as the strict avalanche criterion is satisfied in an unprecedented way!
    For an attacker, things are as a matter of consequence quite nasty as it's not sufficient to decrypt the first few bytes of the file (which are totally sufficient if AES or likewise is attacked). The whole file must be loaded into random access memory and then the entire ciphertext needs to be converted into plaintext and only then it is possible to decide if the selected key was correct or not. That might help to make the challenge difficult.
     
  9. berndroellgen

    berndroellgen Registered Member

    Joined:
    Nov 5, 2010
    Posts:
    59
    My little code-breaking challenge has ended on October 09, 2011, which is exactly four weeks after the geocache was buried. Nobody was able to break the 36 bit code! The geocache was exactly there where I've buried it four weeks ago.

    The password was o5ATrt

    Everybody who wishes to verify the password can download the encrypted video from www.pmc-ciphers.com, as well as the code-breaker tool and decrypt the video with that tool.

    The geocache was buried at the location 47,74664 North 12,01105 East on September 11, 2011.

    Looks as if it's possible to protect (more or less) valuable data with a 6-character password!
    I guess that another challenge in the future requires the treasure to be worth much more. Also it might be a good idea to protect the treasure with a 6-character password and a hint that makes breaking the password easier with a 5-character password. Sounds complicated, but the hint could be a piece of paper that acts as the actual geocache. Maybe somebody here has an idea of how to make such a challenge even more interesting!?
     
  10. x942

    x942 Guest

    No offence, but how many people actually download and attempted to crack it? If no one tried that proves nothing. Send it to Bruce Schnieier I would like a security expert to review it before I trust it at all.

    I too can make brute force a 5 character password impractical, all you need to do is use AES with multiple rounds (encrypting it more than once) keypass does this. If you (for example) encrypt the file 1 time a 5 character password takes the amount of time it takes to test every combination BUT if I encrypt the file 10,000 times you have to use each combination 10,000 times before you know if you decrypted the file/key. Of course 5 characters you should use a lot of rounds (like a few million mine on 1 second delay uses 1.6 million rounds).
     
  11. caspian

    caspian Registered Member

    Joined:
    Jun 17, 2007
    Posts:
    2,301
    Location:
    Oz
    A 5 character password is that easy to crack? How about a 10 character password?
     
  12. x942

    x942 Guest

    10 would be more difficult but still possible 12 is uncrackable by modern computers (except some more powerful computers) and 20+ is the recommended length now a days. Their are some examples of 14 character passwords being cracked. Rainbow tables have gone up to these lengths but don't include ALL combinations. Usually only dictionary words.

    It really depends how much you want to future proof you password and if you are worried about governments or any one with a supercomputer.
     
  13. berndroellgen

    berndroellgen Registered Member

    Joined:
    Nov 5, 2010
    Posts:
    59
    5 or 6 characters are nothing. That's for sure.
    The weird thing about the little 6-character challenge is that the cipher does things somewhat different than other ciphers. That simply enables me to hazard a bunch of silver coins with a ridiculously short password.

    It would be nice to start another challenge in a few feeks or months or so (depending on the weather). I'd like to put more money on the table, but also to make that challenge more attractive. But so far I don't have a good idea how to do that. Password length will again be 6 characters.
    The next challenge should be funny, should again be about some kind of geocache, but all in all it should still be about breaking a password.

    Ideas are really welcome!
     
  14. berndroellgen

    berndroellgen Registered Member

    Joined:
    Nov 5, 2010
    Posts:
    59
  15. berndroellgen

    berndroellgen Registered Member

    Joined:
    Nov 5, 2010
    Posts:
    59
    The 32 bit code breaking challenge remained uncracked !!!

    Even a key as short as 32 bit for a Polymorphic Cipher has proved to remain uncracked in a public challenge that went longer than 4 weeks!

    The exact number of possible key combinations was only 3.724.605.612.
    If approximately half of the total number of human beings on this planet would have chosen a unique keyphrase, one would definitely have won the prize: 1.329 ounces pure gold worth around 2000 USD.

    A standard cipher like AES would in contrast have protected the information less than one hour using a single CPU like an Intel i7 950.
     
  16. Serapis

    Serapis Registered Member

    Joined:
    Nov 15, 2009
    Posts:
    241
    Hmm will I take the word of an marketer making some closedsource home brew encryption or a renowned cryptography expert like Bruce Schneier?

    http://www.schneier.com/blog/archives/2008/10/new_attack_agai.html

    If holding some little known "public contest" makes you feel better about your product then sure go right ahead, but don't imagine for a second that anyone who knows what they're talking about won't see right through it. ;)
     
  17. EncryptedBytes

    EncryptedBytes Registered Member

    Joined:
    Feb 20, 2011
    Posts:
    449
    Location:
    N/A
    I hope you are not just posting these challenges here, but announcing them in actual cracking circles and potential conferences. Because if no one here is doing it, it simply is just security through obscurity.:rolleyes:
     
  18. chiraldude

    chiraldude Registered Member

    Joined:
    Jul 3, 2010
    Posts:
    157
    If you subtract the time required to set up a brute force routine and the time and cost of traveling to whatever GPS coordinates.., $2,000 just isn't worth it for anyone with the required intelligence to give it a try. How about making it worth the effort?

    Try hiding 16 ounces of gold. Maybe even Bruce S. would take a look at it then.
     
  19. berndroellgen

    berndroellgen Registered Member

    Joined:
    Nov 5, 2010
    Posts:
    59
    to Serapis: it was always and it will always be Open Source: -http://downloads.turbocrypt.com/source_code/aes_and_gbpmc_v1_code_breaker_64bit_wo_encryption_routines.zip-

    .. and your renowned cryptography expert appears to miss something. But he always finds nice words. Ridiculing stuff that is not on his agenda must be real fun. Is this good style?

    to EncryptedBytes: The likelyhood that you belong to a certain agency is close to 100%. You obviously do not even conceal where you are located (or it is a fake).
    Announcement in actual cracking circles and potential conferences: Yes, I bet you've got the power to invite me. Simply go ahead.

    The challenge was announced here in this forum (no idea why the thread was moved to some other location) and through two press releases:
    http://www.pressebox.de/pressemeldungen/pmc-ciphers-inc/boxid/474755
    http://www.pressebox.de/pressemeldungen/pmc-ciphers-inc/boxid/474752

    That's definitely more than sufficient. Security by obscurity is certainly something totally different. But: simply help me next time. I really appreciate that!

    To chiraldude: 16 ounces of gold sounds like a decent prize. Bruce S. should although be alarmed by the sheer fact there there is somebody out there who might be able to do things that he hasn't even dreamt about in his wildest dreams. That's worth more than 16 ounces of gold. His reputation is already suffering. What is best about that: These are not even my words!

    And please don't come up with nonsense like "what is protection of short passwords good for". It's in fact all about that! Even worse: If I can show that even very short passwords are safe, then long ones are likely to be much safer.

    If my claims are true, then "experts" like Bruce S. look like beginners. You certainly know very well that 32 bit passwords can be broken in NO TIME, if the cipher is AES, Twofish, DES or whatever lightweight algorithm.

    I come up with open source, a public challenge, information about start and end of the challenge and how to take part through press releases in different languages. What more shall I do? Shall I dance like a bear on TV? Then the comments will be "he's dancing like a freakin' bear, which means that he can only be nuts".

    To whom shall I send personal invitations next time?
    At least I know now what a decent prize shall look like. Thanks for that!
     
    Last edited by a moderator: Feb 13, 2012
  20. Serapis

    Serapis Registered Member

    Joined:
    Nov 15, 2009
    Posts:
    241
    You have misunderstood, I was commenting on the fact that your "proprietary" encryption is not presented for review. You linked to the supposed AES breaker. Why should anyone trust your product when it isn't opensource, expecially when it concerns a mission critical purpose like encryption? There are free opensource alternatives.

    Besides ad hominem attacks against Bruce Schneier, what comaprable credentials do you have to prove your competence in the cryptographic field? Were you a participant in the AES NIST competition? If your discovery is an earth shattering revelation for cryptanalysis of AES, why don't we hear about it outside of this forum? If it were true, the governement would have surely withdrawn its recommendation for it's use for up to the Top Secret level.

    Your product marketing relies on spreading FUD about a heavily and publicly studied cipher which in itself makes me highly doubtful of your competence and motives. Besides that I can't find any concrete evidence from ANY reputable sources recommending your work. Until this fact is addressed no sensible person would put faith in your program.

    I believe that the above are very logical conclusions based on very rational findings and questions. This forum is for discussing proven and effective methods for data security, not for advertising and misinformation.
     
  21. x942

    x942 Guest

    How about not posting FUD on forums? If your amazing cryptography is so good I want you to put up a $50,000 prize for cracking it and actually market the challenge publicly (like on every site you can find).

    I bet it's cracked within 24 - 36 hours if you do that.
     
  22. dantz

    dantz Registered Member

    Joined:
    Jan 19, 2007
    Posts:
    991
    Location:
    Hawaii
    If you really do have something new here then the code needs to be carefully examined by cryptography experts and then put through major testing for weaknesses. Cracking contests don't prove anything.
     
  23. berndroellgen

    berndroellgen Registered Member

    Joined:
    Nov 5, 2010
    Posts:
    59
    Lots of resonance. The discussion seems to be pretty controversial.

    To dantz: Peer review is definitely good. But a code-breaking contest may prove even more: You know, I was on that freakin' tower here in Munich on Sunday morning and I would have given the prize to the first who would have cracked that very short key. That shows commitment. Who wants to lose $2288.54 (today's prize of gold) ? I don't. You most probably as well.

    It also shows something else: NOBODY would protect data worth $2000 with a AES keyphrase reduced to 32 bit! Has nothing to do with FUD but with mathematics.


    to x942: 1 ounce of gold are more appealing to me. But the amount of money that is necessary to "buy credibility for a cipher" appears to rise exponentially in this thread. This is pretty disturbing!
    How much did the participants pay for taking part at the AES contest? Nothing. Correct?


    To Serapis: hmm... I already mentioned that it's open source. That zip archive contains the entire source code.

    Comparable credentials to Bruce S.: Well, when it comes to religion I'm certainly out. In order to become some kind of pope, certain steps need to be taken and it's likely that only believers have a realistic chance.
    A clear advantage of science is that everybody can make discoveries and inventions. There is no monopoly for professors or likewise. Good examples are Michael Faraday and Robert Stirling (a reverent (!!!) who invented the stirling motor). You will certainly agree that the work of these two folks was everything but crap.
    If this forum is although only intended to discuss "proven and effective methods for data security", then obviously this is exactly the right place for me!

    It is a fact that nobody has broken a keyphrase with 32 bit effective length in a public challenge that was announced publically and that went for over one month. The entire source code of the decryption routines of the cipher was and still is publically available as well as source code that is able to break any key with time. The software is even capable of running multiple threads simultaneously in order to speed the exhaustive sieve up. This is even better than peer review by a couple of "experts" as the agenda of those experts might always be questionable. An example will definitely help to understand this circumstance: If the North Korean intelligence agency invents a really nice cipher and all brillant cryptanalysts from that country test the cipher back and forth, would anybody in the rest of the world trust them and use their algorithm? At least I wouldn't.
    But we know that the Enigma was actually broken by the British in WW2. That really counts!!! The machine was not a good design at that time. But German experts claimed that the thing could never be broken.

    So what really counts is an unbiased test. That's exactly what my cipher had to undergo and it has survived. It's only fair that the keysize is reduced to a certain limit that still appears to be safe. For the first challenge the prize was a few silver coins and the keysize was around 36 bit. Until Sunday the prize was over $2000 in gold and the keysize was reduced to 32 bit. There's nothing wrong with that. Next time I have to take a good look at my piggy bank and maybe the prize will be a bit higher and keysize might only be 30 bit. 30 bit are equivalent to approx. 1 billion key combinations. May sound like nothing to you, but there's still a safety margin for me. There is absolutely no way to argument against this. You break it, you get the money (or gold or whatever).

    Serapis: what you write is understandable, but there is a bigger picture and there are massive interests by a certain group of people. A heavily biased perception is the direct result. The background story is very banal.
     
  24. x942

    x942 Guest

    Well first off who uses a 6 character password anyways? How about we see you crack a 20 char. password (AES) first and then we start on your magical cipher?

    Just because your cipher can make brute-forces take longer than plain AES doesn't mean the cipher is better. I can do the same with AES, just re-encrypt it multiple times with the same key.

    If you are so amazing than I want you to crack this file here: http://db.tt/wml7WlMB

    The file is a keepass database.

    It uses a 6 character password and AES256bit. This would normally take 3.28 seconds to crack. I have however increased the number of round substantially. Probably not to the point it's uncrackable but to the point were it would take much more time (like that of a 12 character password). As I said above 6 chars. is weak. Why would anyone use that?However if I did want to I could use that and increase the rounds high enough it would take YEARS to crack.

    If you manage to crack it then post the 200 char. string I put in the file. I generated it using atmospheric noise to guarantee it cannot be produced separately.
     
  25. berndroellgen

    berndroellgen Registered Member

    Joined:
    Nov 5, 2010
    Posts:
    59
    to X942: Among Kerkhoff's principles is this one:
    - The Adversary knows all the details about the cryptosystem
    (algorithms, implementation, etc.), except the secret key.

    Your little challenge violates this principle.

    If the program that you're using is designed properly, then there exist no checksums. As your 200 char plaintext is real random, there is no way to identify the key! In order to successfully mount a brute force attack, the plaintext is required to feature low entropy (little randomness). This is why I've chosen a .MOV file. The header contains lots of zero- and one bit sequences (00000...000 or 1111...1111). Only this enables the adversary to have a realistic chance to identify the key.

    I'm at least that amazing to know this. Should be common sense, although.

    But you've very well understood that AES is weak when it's used with short keys. Let's face it: that was a design criterium! NIST (or whoever formulated the requirements in the late 90's) wanted a block cipher with 128 bit and 128, 192 and 256 bit keys. The thing should also run on little microcontrollers (for smart card applications). Your "thousands of rounds" construction would have had no chance. "Too slow". Another candidate would have been chosen. It's as simple as that. Somebody wants a bicycle and he gets it. Somebody else wants a giant rocket that can reach the moon and there's even someone out there who manufactures that.

    Don't get me wrong: Rijndael is certainly great! I cannot break it when long keys are being used. But there are obvious weaknesses and new cipher designs should eliminate them.

    If you ask average computer users, you will rarely find anybody who uses passphrases that are longer than 6 characters !!!
    It would be good for a modern cipher to protect data that was encrypted with short passwords - if this is technically possible. That's totally logical.

    Another weakness: Modern graphics chips from Nvidia or AMD feature hundreds of processor cores that clever folks use to mount brute force attacks on AES. Well, this very evident weakness of AES can easily be corrected by a cipher that requires quite a lot of resources - more than a little GPU provides. Hardware code breakers are likely to be a real threat anyways.

    I see that you very well feel the same about this free and open source algorithm by offering me a nice challenge with a "pimped cipher".

    Thanks for giving me the opportunity to point out two (obviously pretty new) design criteria for encryption algorithms. At least the first one you've brillantly identified on your own.
     
Thread Status:
Not open for further replies.