The simplicity of the algorithm is largely irrelevant. An xor scheme can be extremely secure if you use a highly-random, one-time pad - which it sounds like YoshiN did.
The excryption cannot be better than that, and it also cannot be any less convienent to use. By some other means, you must share that key with the recipient, and both of you must protect the pad from prying eyes.
If the length of the key is less than the length of the file encrpted, then statistical analysis can lead to clues as to what the key is. For example, the vowels e & a are very common in English text. Knowing that it''s a jpeg gives enough information to attack the encryption. You just concentrate on the header which has known byte values.
e.g. 0xFFD8 FFE0 xxxx 4A46 4946
So right off-the-bat if it''s less than a 32bit key or less, it''s cracked. If it was a 128bit key, it''s now a 96bit key. And there''s more header information. The next two bytes are the length of the FFE0 tag followed by "JFIF". Cracking the length will give a lot more information becase there are more tags in the header with fixed byte values. Odds are really good that the first byte is 0x00 so can assume we''ve cracked 40bits knowing that. The next byte is a mystery for now, but the next 4 bytes (another 32bits) come for free. Next, I would take the first two bytes of the key, and apply them to the next 32 bytes of the jpeg and look for the next tag, 0xFFDB. If this is uncovered, then I have a really good idea how long the key is - and it tells me the length of the 0xFFE0 tag, filling in the missing byte from either. You can continue this process on the rest of the header though it gets trickier from here on out, as the header format is less certain. There''s about 1536 very deterministic bits, and you might be able to push it to 4864bits if you get a little lucky with some assumptions about the header layout.
I do not think blowfish is a sufficent level of encryption to encrypt a straight jpeg. A key length of about 8kbits to 12kbits is called for.
No wonder it''s so easy to break the encryption of DSS''s. They''d have to use poly-megabit keys to stand a chance.
Those types of attacks can be thwarted by injecting a random amounts of random junk into the encrypted file (both of which are also determined by the one-time pad). I''m not sure how to attack this type of encryption, any ideas?
Encryption challenge
quote:Original post by Magmai Kai Holmlor
The simplicity of the algorithm is largely irrelevant. An xor scheme can be extremely secure if you use a highly-random, one-time pad - which it sounds like YoshiN did.
The excryption cannot be better than that, and it also cannot be any less convienent to use. By some other means, you must share that key with the recipient, and both of you must protect the pad from prying eyes.
Yes, it can. If you are to decrypt such a thing, you must use the same pseudo-random number generator. It's called pseudo -random because it's output is totally predictable. So it isn't actually a one-time pad at all.
if you do something like this:
srand(process_key(key));for (int j = 0; j < inp_size / sizeof(unsigned long); j++){ output[j] = input[j] ^ rand();} you can xor the first 32 bits with the JPEG signature or whatever file type it would be, and then just seed the same random number generator with what you get, and just start decrypting from there, using the same algorithm.
For this to actually work, you need to have your own pseudo-random number generator, which must be kept completely secret, and thus be considered part of the key.
quote:
If the length of the key is less than the length of the file encrpted, then statistical analysis can lead to clues as to what the key is. For example, the vowels e & a are very common in English text. Knowing that it's a jpeg gives enough information to attack the encryption. You just concentrate on the header which has known byte values.
e.g. 0xFFD8 FFE0 xxxx 4A46 4946
So right off-the-bat if it's less than a 32bit key or less, it's cracked. If it was a 128bit key, it's now a 96bit key. And there's more header information. The next two bytes are the length of the FFE0 tag followed by "JFIF". Cracking the length will give a lot more information becase there are more tags in the header with fixed byte values. Odds are really good that the first byte is 0x00 so can assume we've cracked 40bits knowing that. The next byte is a mystery for now, but the next 4 bytes (another 32bits) come for free. Next, I would take the first two bytes of the key, and apply them to the next 32 bytes of the jpeg and look for the next tag, 0xFFDB. If this is uncovered, then I have a really good idea how long the key is - and it tells me the length of the 0xFFE0 tag, filling in the missing byte from either. You can continue this process on the rest of the header though it gets trickier from here on out, as the header format is less certain. There's about 1536 very deterministic bits, and you might be able to push it to 4864bits if you get a little lucky with some assumptions about the header layout.
I do not think blowfish is a sufficent level of encryption to encrypt a straight jpeg. A key length of about 8kbits to 12kbits is called for.
Blowfish and other modern symmetrical ciphers do not just encrypt eg. 128 bits, and then move on to the next 128 bits and do the exact same thing to them. If you don't belive me, download the source to blowfish and see for yourself.
There exists two known attacks on blowfish, both of them are only partial breaks, they will not retreive the plaintext. And none of them works on 16-round blowfish or more.
quote:
No wonder it's so easy to break the encryption of DSS's. They'd have to use poly-megabit keys to stand a chance.
Ok, I'm not sure what you mean with DSS, but symmetrical ciphers do not require poly-megabit keys to be secure at all.
edit: NOT fell out.
[edited by - mr BiCEPS on December 4, 2002 5:51:16 PM]
quote:Original post by mr BiCEPS
Yes, it can. If you are to decrypt such a thing, you must use the same pseudo-random number generator. It''s called pseudo -random because it''s output is totally predictable. So it isn''t actually a one-time pad at all.
I wouldn''t consider a pseudo-random number to be "highly random". You need some non-deterministic generator, a giger-counter, noise-bits of the time-delay between key hits (as you suggest), etc... statistically verified for its randomness.
quote:
For this to actually work, you need to have your own pseudo-random number generator, which must be kept completely secret, and thus be considered part of the key.
That''s kinda risky though - it''s only secure until the algorithm is discovered.
With the one-time-pad “cipher”, the key needs to be as random as you can make it, and as long as the data you''re going to send. No pseudo-ness, no repetition, and you can never use that key again.
quote:
Blowfish and other modern symmetrical ciphers do not just encrypt eg. 128 bits, and then move on to the next 128 bits and do the exact same thing to them. If you don''t belive me, download the source to blowfish and see for yourself.
Certainly the key bit-requirement goes down as a more advanced cipher is used. An xor-pad is the worst-case scenario in terms of requisite key-length. Consider the reduction in difficulty when you have the first 1k of the original data file, though. You can work incrementally, drastically reducing the key-space every time you uncover a new byte. I have heard that blowfish is a really-good algorithm, I don’t doubt that. The problem is with the determinism in the source file. Now that I think about it, blowfish is certain to employ some scrambling technique (a rearrangement of the order of the data) – the question of its security for this application is how large the scramble-space is.
quote:
There exists two known attacks on blowfish, both of them are only partial breaks, they will not retreive the plaintext. And none of them works on 16-round blowfish or more.
If I had to guess, both assume no knowledge of the original file.
If I have a copy of the encrypted file and the original, how hard is it to figure out the key used? With a symmetric cipher, isn''t it easy?
quote:
Ok, I''m not sure what you mean with DSS, but symmetrical ciphers do not require poly-megabit keys to be secure at all.
DSS is Digital Satellite System - like Sony Mini-Dish or Dish Network, and now digital cable systems use similar encrypted mpeg2 transport streams. With a limitless supply of deterministic data, and potential access to the unencrypted output, I think it’s impossible to secure it using a symmetric cipher. And if you use an asymmetric cipher, the data’s not really protected, you just know the data is authentic. And now I see why they want the encryption built into TVs and speakers, which would only render "authenticated" sources.
Modern block ciphers generate sub-keys from the main key. These are applied to the plaintext data in various manners to generate the chipertext. The trick is making the process reversible. The Key length does not need to be that large, although a larger key provides greater securtiy against a brute force attack. Most modern chipers use key lengths of 128 or 256 bits.
I've spent this past semster learning this stuff so I can elaborate more on certain issues if you would like.
[edited by - odizzy on December 4, 2002 7:21:34 PM]
I've spent this past semster learning this stuff so I can elaborate more on certain issues if you would like.
[edited by - odizzy on December 4, 2002 7:21:34 PM]
quote:
Oh, sorry, you were talking about real one time pads. The reason I misunderstood you was because you were referencing what YoshiN had done. To me that sounded like pseudo-random pads. The bad thing about real one time pads, though, is that they will never be real-world alternatives to other encryption methods. They will only be as secure as the channel through which you transmit the key. And if you have such a secure channel to use, you might as well use that one on the first place.
I thought this at first too, but you do have multiple means of communication. First, consider military applications. When the sub is at a home port, a large number of keys are delivered to it by wire or by disk. Two large pads for each day for the next year. Then while at sea, they can send and receive one message a day on the air-waves with great secrecy for one year.
For a game application, if you were motivated enough, you put a floppy disk in each box with a sequence of pads in it. Each box gets a different set of keys, and then you need to keep a copy on the server at the home-base. The purpose of those one-time pads are to keep generative keys secret. Upon first run, the game ask for the key disk. Then it demands a password, which it uses as the hash to scramble the pads and store them on the local hard drive. Otherwise, at some point-in-time you have to send some key between the client to the server with a hard-coded key or in plain-text.
quote:
Well, you could figure out all of the subkeys generated, obviously. But the generation of subkeys is in most algorithms (such as Blowfish... oh dear, I'm starting to sound like a blowfish zealot.) a one-way hash-function, so you would still not get the original key.
Is there really such a mathematical beast as a one-way hash?
My mathemagical sense tells me this is impossible. If it used a hashing algorithm that is not 1-to-1, but that means there are multiple keys that would produce the same sequence of subkeys - which is bad. When they say one-way, they must mean an algorithm that does not have a closed-form inverse? I find it hard to believe this is possible without loss of information...
Ah well, I have a copy of Cryptonomicon (a work fiction) around here that has a further crypto reading-list. I'll have to check into them. Anyone have any reading suggestions?
[edited by - Magmai Kai Holmlor on December 5, 2002 2:01:27 AM]
OMG, sorry. The edit & quote buttons are right next to each other and I''m an idiot. I may make a second account to post with. I''ve done that before, but caught it before I hit commit.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
