Re:really undetectable crypto made somewhat practical
I'm on FCPUNX instead of regular Cypherpunks, so please excuse me if I'm a little behind the thread.
New Scheme: First, calculate the MD5 hash of all the words in the various dictionary files used by the password cracker program and create a database containing every word and the first 4 bits of its MD5 hash. Given such a database, it would be possible to write a program that accepts as input a block of cyphertext (the stego message, encrypted), chunks it up in to groups of 4 bits and then, for each chunk, displays the words that have hashes that start with those same four bits. The person running the program would select words that form meaningful sentences but also produce hashes that combine into the encrypted stego message. This scheme would send 4 stego bits per word.
As a slight improvement, you could turn this into a complete stealth encryption scheme, using only the one-way hash function operating as a MAC. Instead of hashing just the word in an effort to get stego bits, you could hash a key along with the word. In order to get the intended hash you would need to know the key. Since you're probably hashing a whole block of 512 bits (or whatever's specified in the algorithm) appending a key should not affect the speed of the system. I'm certain that this would increase the security, possibly enough that you wouldn't need to use a regular encryption algorithm (but I wouldn't bet on it). Crude example: Assume that Alice can use the words "Greetings" and "Salutations" interchangably without drawing suspicion. Also assume that "PASSWD" is a secret known only to Alice and Bob, and that the stego software looks at the low bit of an MD5 hash. MD5 ("GreetingsPASSWD") = c7bf6e051731a0dcf52baa330c9d2e7d <- low bit=1 MD5 ("SalutationsPASSWD") = 2dd2ba080b5feb060ffbc6d196fd1b34 <- low bit=0 If you say "Greetings" you're sending a 1, if you say "Salutations" you're sending a 0. Eve doesn't know about "PASSWD" so she can't do the hash and figure the bit. Of course, if you're using this to send more bits, you'll need something harder to guess than "PASSWD". The trick is in figuring out which words have stego bits and which don't. It might be better to stego bits into a whole line instead of a word, as that would probably offer more flexibility. ===================================================================== | Steve Reid - SysAdmin & Pres, EDM Web (http://www.edmweb.com/) | | Email: steve@edmweb.com Home Page: http://www.edmweb.com/steve/ | | PGP (2048/9F317269) Fingerprint: 11C89D1CD67287E68C09EC52443F8830 | | -- Disclaimer: JMHO, YMMV, TANSTAAFL, IANAL. -- | ===================================================================:)
I'm on FCPUNX instead of regular Cypherpunks, so please excuse me if I'm a little behind the thread.
Few on the cypherpunk list replied to my post, so you didn't miss anything important.
Instead of hashing just the word in an effort to get stego bits, you could hash a key along with the word. In order to get the intended hash you would need to know the key. Since you're probably hashing a whole block of 512 bits (or whatever's specified in the algorithm) appending a key should not affect the speed of the system. I'm certain that this would increase the security, possibly enough that you wouldn't need to use a regular encryption algorithm (but I wouldn't bet on it).
I like your suggestion, although not for the reason you suggested it (although your use is a good idea, too). The use of keyed hashes solves one of the problems I saw with my scheme. The main problem I saw with my scheme was that it might be possible to detect that an innocuous message was conveying a hidden encrypted message by analyzing the statistical properties of the relevant hash bits. Problem: If the words in a message are chosen so some of their hash bits (say, 4 bits per hash) combine to form an encrypted message, then those combined hash bits would be suspiciously cryptographically random, whereas the combined hash bits of a message that was not created for the purpose of conveying an encrypted message would not necessarily be cryptographically random. It is conceivable that a program could be written that uses this difference to test if a message is conveying a hidden encrypted message. Solution: Rather than using an unkeyed hash, which gives Eve the ability to generate the relevant block of combined hash bits and test them for certain properties, use a keyed hash. Since Eve does not know the key used to hash the words in the message, she will not be able to generate the relevant block of combined hash bits and will not be able to perform meaningful analysis of the properties of those bits. Further analysis: By hashing words and then using only the first 4 hash bits, what you are really doing is sorting all words into 16 groups. Group 0 consists of all words whose first four hash bits are 0000, group 1 consists of all words whose first four hash bits are 0001, ..., group 15 consists of all words whose first four hash bits are 1111. If a message is constructed by selecting words so their first 4 hash bits combine to form an encrypted message, then, if the message is long enough or you send enough messages, you will probably select words "evenly" from each of the 16 word groups. However, I can think of no reason to assume the distribution of group selections would be "even" for normal messages. Maybe, by some weird fluke, normal messages are mostly constructed from words in groups 1, 3, 4, 9, and 14, for example. By using a keyed hash, your not stuck using a fixed set of word groups. A different hash key will sort the words into different groups. Hash keys effectively prevent Eve from knowing which words in your message came from which groups, thus preventing her from determining if words were chosen "evenly" from each group. Jim_Miller@suite.com
participants (2)
-
Jim Miller -
Steve Reid