Cryptic security



  • I've been doing some work on the cross-platform compatibility library our company uses.  Just on a whim, I decided to look at the encryption support in the library.  It supplies two encryption algorithms you can choose between: the venerable DES cipher (the header file has warnings about how this cipher may not be secure), and...


    ...the Vigenere cipher.



  • [quote user="Carnildo"]I've been doing some work on the cross-platform compatibility library our company uses.  Just on a whim, I decided to look at the encryption support in the library.  It supplies two encryption algorithms you can choose between: the venerable DES cipher (the header file has warnings about how this cipher may not be secure), and...


    ...the Vigenere cipher.

    [/quote]

    Wow, someone never made it past the second Cryptology lecture. And who needs books anyway. Not to mention ssl libraries. Too easy.



  • Why not throw in Caesar, rot13 and pig latin also? ;)



  • The dev was probably told by lawyers to do it this way so that they could sue anyone who deciphered it.



  • @Guffa said:

    Why not throw in Caesar, rot13 and pig latin also? ;)

    Is Pig Latin de-cypherable by an algorithm? We should explore this.



  • If DES had a caveat "not the most secure thing around", did Vignere have a caveat?  It would be pretty funny if someone read the DES header, and then used Vignere instead, because the data really was sensitive.



  • Alright the vigenere cipher is way easy to crack where the code space is reduced by short code phrases and sequential ciphers for each letter of the code phrase, but is it that bad when its used correctly?

    If each row of the cipher matrix is as random as possible, and the code phrase to encode the text is large (say 15+ individual chars and not easily predictable), is it easily crackable?



  • [quote user="huh"]

    If DES had a caveat "not the most secure thing around", did Vignere have a caveat?  It would be pretty funny if someone read the DES header, and then used Vignere instead, because the data really was sensitive.

    [/quote]

    No disclaimer.  Admittedly, this code was written back when DES was still somewhat viable -- nobody had admitted to having built a dedicated DES cracker, but the possibility existed -- but there were still plenty of ciphers floating around that hadn't been cracked 130 years earlier.



  • [quote user="bloodangel"]

    Alright the vigenere cipher is way easy to crack where the code space is reduced by short code phrases and sequential ciphers for each letter of the code phrase, but is it that bad when its used correctly?

    If each row of the cipher matrix is as random as possible, and the code phrase to encode the text is large (say 15+ individual chars and not easily predictable), is it easily crackable?

    [/quote]

    I'm not a cryptanalyst, but based on a cursory review it appears that your suggestions don't make Vigenere significantly harder to break, given sufficient ciphertext.  The standard attack on Vigenere or other polyalphabetic substitution ciphers is to determine the key length by measuring the index of coincidence of the ciphertext at various trial key lengths.

    If the key length is much smaller than the ciphertext length, it's easy to determine the key length this way.  Given a decent amount of ciphertext, automated analysis ought to be able to determine a key length on the order of 15 in negligible time.

    Once the key length N is known, the breaking the cipher reduces to breaking N Caesar ciphers, which is easily done by frequency analysis if there's enough ciphertext, enough is known about the plaintext (eg that it's English text), and the plaintext has sufficiently low entropy (as is the case for English text, and lots of other sorts of data).

    --

    Michael Wojcik 



  • [quote user="bloodangel"]

    Alright the vigenere cipher is way easy to crack where the code space is reduced by short code phrases and sequential ciphers for each letter of the code phrase, but is it that bad when its used correctly?

    If each row of the cipher matrix is as random as possible, and the code phrase to encode the text is large (say 15+ individual chars and not easily predictable), is it easily crackable?

    [/quote]

    If you do some research you'll find that, long story short, a Vigenere-encoded message can be trivially broken down into a set of single-substitution cyphers.  Then you just have a set of frequency analysis tasks.
     



  • [quote user="djork"][quote user="Guffa"]

    Why not throw in Caesar, rot13 and pig latin also? ;)

    [/quote]

    Is Pig Latin de-cypherable by an algorithm? We should explore this.[/quote]

    There was a shareware Dos/EGA Desktop Publishing package that used decipherable pig latin: Apart from the 'loreum Ipsum" bit, it was a promotional speel with promises of T-shirts etc to the first person who contacted them, with every word reversed. I'm sure I'll remember the name of it sometime tonight. 



  • It was PagePlus (yub sulpegap won!, backwards)



  • If your key is as long as the message and consists of randomly chosen letters, is it then secure? I'd be inclined to believe yes, although choosing a key and getting it to the intended recipient could be a problem.

    For example, the standard "xor the data with the key" encryption is extremely insecure, but if you seeded a (good/complex) pseudo-random number generator with the key and xor'ed the results of the random number generator with your message, how secure would that be, with a moderately long key (say 256 random bits)? 

     



  • [quote user="bobday"]If your key is as long as the message and consists of randomly chosen letters, is it then secure? I'd be inclined to believe yes, although choosing a key and getting it to the intended recipient could be a problem.[/quote]

    That's known as a one-time pad, and if done correctly, yes, it would be secure. As evidenced by the name, though, you'd need to only use the key once, and then never again. The characters would also have to be truly random - no pseudo-randomness allowed.

    One-time pads, if done correctly, are impossible to crack since you could 'decode' the message into every possible sequence of letters - 'oijxeoinsxiomsxd' *could* mean 'attackarmyatnoon', but it could equally mean 'weadorechocolate' or 'aflyingpigishere'. ;-)



  • But, you need to be able to transfer the key securely ... and if the key is as long as the message, you might almost as well transfer the message securely if you can do that.



  • [quote user="Bob Janova"]But, you need to be able to transfer the key securely ... and if the key is as long as the message, you might almost as well transfer the message securely if you can do that.
    [/quote]

    One time pads have entirely different applications, namely where lots of keys can be transmitted securely at once, but future messages/keys will not have that luxury. (A spy embedded in hostile teritory is the classic use.) If your pad is compromised, you're up a creek until you can get a new one, unless you can do Diffie-Hellman negotiation over snail mail. (Which didn't even exist until 1976.)

    Obviously the more secure method here would be implement your own double-rot-13. 



  • One time pads have entirely different applications, namely where lots of keys can be transmitted securely at once, but future messages/keys will not have that luxury. (A spy embedded in hostile teritory is the classic use.) If your pad is compromised, you're up a creek until you can get a new one, unless you can do Diffie-Hellman negotiation over snail mail. (Which didn't even exist until 1976.)

    Yeah, I know. But computer cryptography isn't usually used in such a situation. I guess something like off-site work where you can transmit a bunch of keys over the LAN to a laptop which the off-site guy then uses would be suitable.

     Hehe, you make it sound like snail mail didn't exist in '76 ;).

    The other problem is if a message gets lost, you are screwed from then on as the keys are out of sync. But that's not too hard to avoid.

Log in to reply