still no response on how he cracked public key encryption. This forum has got me interested in OTP though and I am looking to create an open source key generator and hardware message encrypter.
For the message transmittion direct ip to ip communication would be best if both are online. If not though a server would probably be best since e-mails can get lost really easily.
I am willing to set aside 100TB of space on my web server indefinitely for temporary storage of encrypted messages until they have been read. Since OTP can only be read once I can set it up to delete the message off the server after the hardware verifies it got the whole message.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
Here is a fascinating description of the Lorenz Cipher and discusses the difference between decoding Lorenz teletype machines (and Siemens teletype machines which aren't discusses here but were also cracked) and Enigma Morse code messages. You will see why the Colossus computer was a 5-bit machine. Teletype machines used the 5 channel· Bardot code (5 cables and ground ran between each station)
Have a look at those circuit diagrams on page 2. I wonder what CAD package they used to draw them.· I thought the Colossus was run from Dollis Hill but Wikipedia says it·WAS at Bletchley Park.
You’ll see that·Colosus was operator programmable. The article says there were 10 computers but Tom Flowers' biography spoke of only three, and only two were completed before the end of the European hostilities.
Tom Flowers was asked to revamp the Heath Robinson after the success of the Colosus computer but these remaind mechanical devices for pattern recognition.
John Bond said...
Teletype machines used the 5 channel Bardot code (5 cables and ground ran between each station)
Was that the Bridget Bardot code? Actually it was the Baudot code, which is where the word "baud" comes from. The Baudot code was capable of handling thirty characters in each of two different ranks or "shifts", plus two shift commands (LTRS & FIGS). Some control characters were common to both ranks to avoid extraneous shifting.
I'm not sure about the cited 6-wire interface either. The Baudot teletype I had once transmitted and received the bits serially over a two-wire (signal + ground) interface. It was entirely electromechanical, the only electrical components being a motor and some solenoids — quite the mechanical monstrosity.
Dang it, Carl! "Stecker" isn't in my Compact OED. Enthralled with learning a new word, I was all set to bait a challenge the next time I played Scrabble (and got the right letters). 'Found it in the English/German dictionary, though (as a noun), but that doesn't add to my point score without an effective bluff!
-Phil
Where's Rich?!!! He's still got some splainin' to do!
Pursuant to the OTP discussion, mctrivia brings up a good point in this thread that brings into question the desirability of strict independence in generating random variables for an OTP. Consider the case where one is simply XORing the plaintext with the OTP to create the ciphertext. A truly independent random sequence could well (but infrequently) include long runs of the same symbol. A short message encoded with such a repeating portion of the OTP would be no better than one created with a substitution cipher. I think there needs to be a stricter standard than independence. Perhaps imposing a minimum value on the entropy of the OTP at multiple scales is a workable approach. IOW, it not only has to be random, but also has to look random.
Actually, Phil, that's a trap.· Avoidance of strings of duplicates in the OTP actually provides a way to get a wedge into the cipher.· In a random string (OTP) with 256 possible values, for example, one character out of 256 (on average) will be followed by the same identical character.· One out of 65536 will be followed by two characters identical to itself, etc.· Longer strings will be very rare.· Strings of four will occur every 16777216 characters, etc.·
In general, cryptographers don't (and can't) break single short messages of any but the simplest ciphers.· Even a simple substitution cipher (such as the weekly Crypto-Quip in daily newspapers, which I usually solve in my head without writing anything down) have to be longer than "several" characters long to be breakable.
Rejewski determined that, for the Enigma,·cryptanalysis requires a minimum, usually, of 80 to 100 messages encrypted using the same settings (same key).
It is true that a message encrypted by the method you posit might contain short sequences that are in effect enciphered monalphabetically.· But, with precisely equal probability, it will contain sequences that only appear so, but lead to an entirely erroneous decrypt.· In fact, such sequences will appear, also with exactly equal frequency, in the OTP itself.
Any operation that works on a truly random string, and processes it to remove anything that looks nonrandom, will be introducing, not eliminating,·departures from randomness.
I trust that you found out what a stecker board was, as applied to those versions of Enigma that had them.· Enigmas with stecker boards were said to be "steckered".· Most German·ones were steckered in WW2, but the Italians and some few low-level German·message systems used unsteckered Enigmas, which were correspondingly easier to solve.· This was an occasional bonanza for the folks at Bletchley Park, because high-level messages in a difficult cipher were sometimes repeated to lower-level commands in unsteckered ciphers, thus giving B.P. an opportunity to possess the same message in an easy and a difficult cipher.· Breaking the easy cipher gave a plaintext of a message in the difficult cipher, which greatly eased breaking of the hard one for subsequent messages.
Carl Hayes said...
Any operation that works on a truly random string, and processes it to remove anything that looks nonrandom, will be introducing, not eliminating, departures from randomness.
Minor quibble: I think it's necessary to distinguish randomness from independence. Many sequences can be truly random but not independent, such as Markov chains. The treatment I was proposing (guaranteeing high levels of entropy at multiple scales) compromises independence, but the sequence may still be considered random. The probability distribution of each element, however, is a (weak) function of what came before.
I guess the determining question is this: If your OTP had a portion with a long string of identical characters (highly unlikely, hence suspect, but nonetheless possible), would you use it or discard it?
Thanks for the additional info about "Stecker" boards. My English/German dictionary only translates "Stecker" as "connector".
-Phil
Addencum: A better way to come up with an OTP might be to generate the sequence as independent samples, then test the entire string for the entropy condition. If it passes, keep it; otherwise start over. That way the sample-to-sample independence will be only weakly compromised without introducing an overt element of determinism.
Post Edited (Phil Pilgrim (PhiPi)) : 4/10/2009 7:52:30 PM GMT
I would use with exception of really long string of 0s or 1s which could leave a key word completely visible. sure the words could be statistical inomally but would rather someone not see it.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
Carl Hayes said...
Any operation that works on a truly random string, and processes it to remove anything that looks nonrandom, will be introducing, not eliminating, departures from randomness.
Minor quibble: I think it's necessary to distinguish randomness from independence. Many sequences can be truly random but not independent, such as Markov chains. The treatment I was proposing (guaranteeing high levels of entropy at multiple scales) compromises independence, but the sequence may still be considered random. The probability distribution of each element, however, is a (weak) function of what came before.
I guess the determining question is this: If your OTP had a portion with a long string of identical characters (highly unlikely, hence suspect, but nonetheless possible), would you use it or discard it?
Thanks for the additional info about "Stecker" boards. My English/German dictionary only translates "Stecker" as "connector".
-Phil
I wouldn't even be aware of it.· Who wants to look through a 3GB file of random bytes to search for stuff like that?· Of course I'd use it.
Using your system of ringsumming (that is, XORing) the plaintext with the key byte-for-byte, let us suppose, for example, that the key contains fifteen consecutive zeros.· If the plaintext happens to contain the string kill the umpire [noparse][[/noparse]the title of a William Bendix movie] in that position, the ciphertext will also contain the string kill the umpire.· But that string would occur in the ciphertext anyway, with exactly the same probability, even if the plaintext had nothing like it.· So it isn't a weakness because it won't stand out statistically.· It's expected that it will occur, though·rarely -- and how rarely is known.
On the other hand, suppose our plaintext includes the word "bookkeeper".· This contains·two of the most common double-letter sequences in English (oo and ee).· It also contains a rare one, kk.· On average, a double letter in the plaintext will result in a double character in the ciphertext once in 256 times if the key is random.· Any cryptanalyst worth his Cray knows the frequency of double letters in English, and knows how often they'd cause doubles in the ciphertext if the key is random.· If we eliminate doubles from the key, we will reduce incidence of doubles in the ciphertext.· We won't be increasing their incidence elsewhere (because not all letter pairs occur with equal frequency in English, and we have increased the incidence of all non-double pairs in the key), so the cryptanalyst will see a departure from randomness in the ciphertext.· For him, that's a start.· Is it enough of a start?· I have no idea, but I'll bet NSA (a) could answer it, and (b) won't.
Same argument applies for triples, quads, etc.
English for "Stecker" is usually "plug".· A stecker board is a plugboard.· In Enigmas it was used to make a symmetrical swap of letters in a letter pair (as, substituting ax for xa), at the input.· German use of steckers always was symmetrical in this way, which fact was useful in designing the second and subsequent bombes.
Incidentally, we have given our imaginary cryptanalyst another help.· If we eliminate doubles from the key, he will figure that out from the wobble we've inserted.· Then he will know that any double in the ciphertext cannot be a double in the plaintext.
Me, I don't want him to figure out anything about the plaintext.· Do you?
now my suggestion of forcing the key to never contain more then 21 repeating bits in a row only removes 1 combinations in 1000000 and does not give anything statistically important away other then if they see a word longer then 21 bits then it is not what it looks like.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
Okay, let's suppose we don't eliminate doubles explicitly, but proceed as in my addendum above. We'll measure the entropy at multiple scales beginning at n characters and working on up from there to m (> n) characters. If the sequence fails the test, we throw the whole thing out and start over. Obviously, the test can't be too stringent, or we'd never be able to come up with a good OTP. Under those circumstances, I would defy any NSAer, once the OTP is XORed with the plaintext, to infer any kind of pattern that would provide a wedge for analysis.
-Phil
(Frankly, I'm not at all certain how to measure the OTP's entropy. Zip it, perhaps, and see how much shorter it gets? I need to brush up on Shannon's work.)
A Russian OTP system was cracked in 1944 because people avoided doubles in the key·since they didn't look random (and because they reused part of the same keypad in a separate system).· A truly random sequence can have any substring within it.· Cutting out certain strings for any criterion at all makes it not random.· You will be taking extra precautions to make your encryption system·insecure -- something the Germans did over and over in WW2.
Again, and I'm sorry to correct, but one really has to be careful about mixing up "randomness" with "independence". They're not the same thing. All too often, when one says "random", they mean "independently random" and assume that just because independence is compromised, so is randomness.
But independence is not a necessary precondition for randomness. My suggestion is to relax the condition for independence very slightly by taking a measurement on the entire string and throwing it out if certain entropy conditions are not met. This does not a priori discard doublets, triplets, or even octuplets. But it would, hopefully, remove from consideration strings that have compromisable traits.
The point is that any string that's accepted was, from the outset, generated by an independently random process — the same as you use, perhaps, and a string which you would not reject, since you don't reject any of them. Hence any "taint" left by the selection process would necessarily be undetectable (unless the process of selection leaves some sort of homeopathic "imprint" ).
Another way of looking at this is to generate several thousand candidate strings and put them in an urn. You would agree that any one that's selected from the urn is as good as any other one, right? So if you pick one at random and I sort through them looking for one that I like, how is the random selection any better than the one given more scrutiny?
Now obviously, if I were too picky, this might show up over the course of many selections as a statistical quirk. But I doubt that the traits I'd be selecting for would ring any bells over a thousand lifetimes of generating OTPs.
curios no one comments on my suggestion of 1 single limit no more then 21 same value bits in a row. statistically happens rarely to start.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
Randomness, in the sense you use the term,·is not sufficient.·
Suppose, for example, that I used as a key a string of bytes from 0 to 255 with a Gaussian distribution (instead of a level one) with a mean (and median and mode) equal to 127, and a standard deviatiion of three.·
Such a keyfile could be perfectly random (it's in perfectly random order) but it's rather extremely biased, and my cipher would be very easy to break.
Fractal sequences are also biased -- the probability of a paricular value at any position in the string depends upon what has gone before.· That biases the distribution of digraphs in the keyfile, and of trigraphs even more, etc.· Those are serious faults in a keyfile.· If some digraphs are more probable than others·in the keyfile (because it's not, as you term it, independent), and some digraphs are more probable in the plaintext (because it's a human language), then the most frequent digraphs in the ciphertext will certainly represent the most frequent digraphs in the plaintext.· That kind of result is exactly what statistical cryptanalysis feeds upon.· And a few percent is a lot of wobble in a digraph distribution, for moderately long ciphertexts.·
Even if it were not so, I see no possible benefit in doing as you suggest.· It's a waste of processing.· As I understand it, you want to make the keyfile look random to human eyes.· Why?· If the opponent ever gets to see the keyfile, you're done for anyway.
Why would anyone take what you call an "independently random" key sequence and change it into something that isn't?· Seems wacko to me.
However, any problems caused by it will be yours, because those are mistakes I don't intend to make.· I'm sure I can invent other mistakes that are peculiarly my own.
The thing is that an encoded message doesn't occur in isolation. A potential attacker may know a lot about the sender and the receiver, along with the context of the message. In the rare event that a long string of zeroes appears in the key, say, he would thus be able to infer that he was reading plaintext and not some equally statistically flukey transformation of the plaintext into something else that's readable. For this reason, I'm not convinced that a strict adherence to statistical independence is the best route when other dependencies (foreknowledge, context, etc.) exist. Granted, the probability of an event like I describe is exceedingly small, and from any practical standpoint, perhaps zero. But from a theoretical standpoint it makes for an interesting discussion. My point of view is that the process of OTP selection can be guided just a little to minimize the consequences of those other dependencies.
In the rare event that a long string of zeroes appears in the key, say, he would thus be able to infer that he was reading plaintext
And according to quantum mechanics, the cookie I just ate could have jumped off the table instead of waiting while I reached for it and grasped it.
It needn't be zeroes -- a string of any other value would serve the cryptanalyst nearly as well.· Have you calculated just how rare that rare event is?·
It's exceedingly rare.· Reading ten characters of the message probably wouldn't avail him much, but in order for the ciphertext to contain ten characters of consecutive plaintext, there would have to be ten consecutive zeros in the keyfile.· That will happen just more than once in 1024 bytes of "independently random" key.· My keyfiles are 3 GB in length.· So it will occur in about one out of 4x1014 of my 3 GB keyfiles.· That's once in 400 trillionkeyfiles, each of which will probably encrypt at least several thousand·plaintexts that I may wish to send over the Internet.· I have a greater chance to be killed by an impacting meteor tomorrow.
Engineering is the science of calculating what is sufficient.
but it is still possible. the question is would adding a little code to remove a long string of 0 harm the otp
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
by the way anyone have the letter odds and how often doubles etc happen I can't seem to find my list
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
mctrivia said...
but it is still possible. the question is would adding a little code to remove a long string of 0 harm the otp
Yes, it would make the OTP less secure.
If the keyfile is random, and the encipherment is, say, a simple XOR, then the ciphertext will be equally random.· Ifnot, not.
The cryptanalyst will examine the ciphertext to determine, among other things, in what ways it departs from randomness.·Any test you can perform to find strings to remove from the key, the cryptanalyst can perform on the ciphertext·to find out what kind of strings you removed.· The more you do of that kind of thing, the more the cryptanalyst can infer about your keyfiles.
In a random byte-oriented keyfile, 00 [noparse][[/noparse]hex] will be followed by 00 one time out of 256, and by 0000 one time out of 65536.· If you remove all strings of, say, three or more zeros, these 0000 strings will be less frequent than expected (when you remove 000000, you are removing two occurrences of 0000).· Since the character set of English doesn't use even half the 256 possible bytes, and isn't random at all, the ciphertext will contain hints of what you did.
If the keyfile is random (what Phil calls·independently random), it will contain, say, "000000" [noparse][[/noparse]hex] with a certain frequency [noparse][[/noparse]once in 65536 bytes].· If you remove them, then the ciphertext will contain fewer possible products of such a keystring than it would normally contain.· The digraph "th", for example,·is·very common in English.· If you remove all sequences of, say, three or more zeroes in the keyfile, there will be fewer·"0000" keysequences·than the 1/256 normally expected, and there will be fewer digraphs "th" than normally expected in the ciphertext.· So the cryptanalyst can figure out you did that, or something like that.· That is, if you look for those and remove them, the cryptanalyst will discover that you did so, and he can then assume that no part of the plaintext was enciphered with such a string.· So he will know more about·your keyfile, and·the relation between your plaintext and your ciphertext, than he would know if you did nothing.· For example, if he figures out that you took out all 0000 strings, he can assume that "th" in the ciphertext is never "th" in the plaintext.· He can make the same assumpion about every other digraph, too.
If I·remember right there was professional software around some time back that allowed you to embed encrypted text and other files including other pictures·into a picture file you could see the picture unnaffected but without the software you couldnt extract the files etc
I am not suggesting removing 000000 from the file in that way. instead if the 16k cluster contains 000000 delete it and start over this will keep 0000 the same odds
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
Comments
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
http://forums.parallax.com/showthread.php?p=798301 - key generator
For the message transmittion direct ip to ip communication would be best if both are online. If not though a server would probably be best since e-mails can get lost really easily.
I am willing to set aside 100TB of space on my web server indefinitely for temporary storage of encrypted messages until they have been read. Since OTP can only be read once I can set it up to delete the message off the server after the hardware verifies it got the whole message.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
http://www.codesandciphers.org.uk/lorenz/fish.htm
Have a look at those circuit diagrams on page 2. I wonder what CAD package they used to draw them.
http://en.wikipedia.org/wiki/Colossus_computer
You’ll see that·Colosus was operator programmable. The article says there were 10 computers but Tom Flowers' biography spoke of only three, and only two were completed before the end of the European hostilities.
Tom Flowers was asked to revamp the Heath Robinson after the success of the Colosus computer but these remaind mechanical devices for pattern recognition.
Tom Flowers·was an amazing guy...
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I'm not sure about the cited 6-wire interface either. The Baudot teletype I had once transmitted and received the bits serially over a two-wire (signal + ground) interface. It was entirely electromechanical, the only electrical components being a motor and some solenoids — quite the mechanical monstrosity.
-Phil
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
-Phil
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
-Phil
Where's Rich?!!! He's still got some splainin' to do!
-Phil
In general, cryptographers don't (and can't) break single short messages of any but the simplest ciphers.· Even a simple substitution cipher (such as the weekly Crypto-Quip in daily newspapers, which I usually solve in my head without writing anything down) have to be longer than "several" characters long to be breakable.
Rejewski determined that, for the Enigma,·cryptanalysis requires a minimum, usually, of 80 to 100 messages encrypted using the same settings (same key).
It is true that a message encrypted by the method you posit might contain short sequences that are in effect enciphered monalphabetically.· But, with precisely equal probability, it will contain sequences that only appear so, but lead to an entirely erroneous decrypt.· In fact, such sequences will appear, also with exactly equal frequency, in the OTP itself.
Any operation that works on a truly random string, and processes it to remove anything that looks nonrandom, will be introducing, not eliminating,·departures from randomness.
I trust that you found out what a stecker board was, as applied to those versions of Enigma that had them.· Enigmas with stecker boards were said to be "steckered".· Most German·ones were steckered in WW2, but the Italians and some few low-level German·message systems used unsteckered Enigmas, which were correspondingly easier to solve.· This was an occasional bonanza for the folks at Bletchley Park, because high-level messages in a difficult cipher were sometimes repeated to lower-level commands in unsteckered ciphers, thus giving B.P. an opportunity to possess the same message in an easy and a difficult cipher.· Breaking the easy cipher gave a plaintext of a message in the difficult cipher, which greatly eased breaking of the hard one for subsequent messages.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
Post Edited (Carl Hayes) : 4/10/2009 7:21:17 PM GMT
I guess the determining question is this: If your OTP had a portion with a long string of identical characters (highly unlikely, hence suspect, but nonetheless possible), would you use it or discard it?
Thanks for the additional info about "Stecker" boards. My English/German dictionary only translates "Stecker" as "connector".
-Phil
Addencum: A better way to come up with an OTP might be to generate the sequence as independent samples, then test the entire string for the entropy condition. If it passes, keep it; otherwise start over. That way the sample-to-sample independence will be only weakly compromised without introducing an overt element of determinism.
Post Edited (Phil Pilgrim (PhiPi)) : 4/10/2009 7:52:30 PM GMT
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
Using your system of ringsumming (that is, XORing) the plaintext with the key byte-for-byte, let us suppose, for example, that the key contains fifteen consecutive zeros.· If the plaintext happens to contain the string kill the umpire [noparse][[/noparse]the title of a William Bendix movie] in that position, the ciphertext will also contain the string kill the umpire.· But that string would occur in the ciphertext anyway, with exactly the same probability, even if the plaintext had nothing like it.· So it isn't a weakness because it won't stand out statistically.· It's expected that it will occur, though·rarely -- and how rarely is known.
On the other hand, suppose our plaintext includes the word "bookkeeper".· This contains·two of the most common double-letter sequences in English (oo and ee).· It also contains a rare one, kk.· On average, a double letter in the plaintext will result in a double character in the ciphertext once in 256 times if the key is random.· Any cryptanalyst worth his Cray knows the frequency of double letters in English, and knows how often they'd cause doubles in the ciphertext if the key is random.· If we eliminate doubles from the key, we will reduce incidence of doubles in the ciphertext.· We won't be increasing their incidence elsewhere (because not all letter pairs occur with equal frequency in English, and we have increased the incidence of all non-double pairs in the key), so the cryptanalyst will see a departure from randomness in the ciphertext.· For him, that's a start.· Is it enough of a start?· I have no idea, but I'll bet NSA (a) could answer it, and (b) won't.
Same argument applies for triples, quads, etc.
English for "Stecker" is usually "plug".· A stecker board is a plugboard.· In Enigmas it was used to make a symmetrical swap of letters in a letter pair (as, substituting ax for xa), at the input.· German use of steckers always was symmetrical in this way, which fact was useful in designing the second and subsequent bombes.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
Post Edited (Carl Hayes) : 4/10/2009 8:18:03 PM GMT
Me, I don't want him to figure out anything about the plaintext.· Do you?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
-Phil
(Frankly, I'm not at all certain how to measure the OTP's entropy. Zip it, perhaps, and see how much shorter it gets? I need to brush up on Shannon's work.)
A Russian OTP system was cracked in 1944 because people avoided doubles in the key·since they didn't look random (and because they reused part of the same keypad in a separate system).· A truly random sequence can have any substring within it.· Cutting out certain strings for any criterion at all makes it not random.· You will be taking extra precautions to make your encryption system·insecure -- something the Germans did over and over in WW2.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
Post Edited (Carl Hayes) : 4/12/2009 1:43:01 AM GMT
Again, and I'm sorry to correct, but one really has to be careful about mixing up "randomness" with "independence". They're not the same thing. All too often, when one says "random", they mean "independently random" and assume that just because independence is compromised, so is randomness.
But independence is not a necessary precondition for randomness. My suggestion is to relax the condition for independence very slightly by taking a measurement on the entire string and throwing it out if certain entropy conditions are not met. This does not a priori discard doublets, triplets, or even octuplets. But it would, hopefully, remove from consideration strings that have compromisable traits.
The point is that any string that's accepted was, from the outset, generated by an independently random process — the same as you use, perhaps, and a string which you would not reject, since you don't reject any of them. Hence any "taint" left by the selection process would necessarily be undetectable (unless the process of selection leaves some sort of homeopathic "imprint"
Another way of looking at this is to generate several thousand candidate strings and put them in an urn. You would agree that any one that's selected from the urn is as good as any other one, right? So if you pick one at random and I sort through them looking for one that I like, how is the random selection any better than the one given more scrutiny?
Now obviously, if I were too picky, this might show up over the course of many selections as a statistical quirk. But I doubt that the traits I'd be selecting for would ring any bells over a thousand lifetimes of generating OTPs.
-Phil
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
Suppose, for example, that I used as a key a string of bytes from 0 to 255 with a Gaussian distribution (instead of a level one) with a mean (and median and mode) equal to 127, and a standard deviatiion of three.·
Such a keyfile could be perfectly random (it's in perfectly random order) but it's rather extremely biased, and my cipher would be very easy to break.
Fractal sequences are also biased -- the probability of a paricular value at any position in the string depends upon what has gone before.· That biases the distribution of digraphs in the keyfile, and of trigraphs even more, etc.· Those are serious faults in a keyfile.· If some digraphs are more probable than others·in the keyfile (because it's not, as you term it, independent), and some digraphs are more probable in the plaintext (because it's a human language), then the most frequent digraphs in the ciphertext will certainly represent the most frequent digraphs in the plaintext.· That kind of result is exactly what statistical cryptanalysis feeds upon.· And a few percent is a lot of wobble in a digraph distribution, for moderately long ciphertexts.·
Even if it were not so, I see no possible benefit in doing as you suggest.· It's a waste of processing.· As I understand it, you want to make the keyfile look random to human eyes.· Why?· If the opponent ever gets to see the keyfile, you're done for anyway.
Why would anyone take what you call an "independently random" key sequence and change it into something that isn't?· Seems wacko to me.
However, any problems caused by it will be yours, because those are mistakes I don't intend to make.· I'm sure I can invent other mistakes that are peculiarly my own.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
The thing is that an encoded message doesn't occur in isolation. A potential attacker may know a lot about the sender and the receiver, along with the context of the message. In the rare event that a long string of zeroes appears in the key, say, he would thus be able to infer that he was reading plaintext and not some equally statistically flukey transformation of the plaintext into something else that's readable. For this reason, I'm not convinced that a strict adherence to statistical independence is the best route when other dependencies (foreknowledge, context, etc.) exist. Granted, the probability of an event like I describe is exceedingly small, and from any practical standpoint, perhaps zero. But from a theoretical standpoint it makes for an interesting discussion. My point of view is that the process of OTP selection can be guided just a little to minimize the consequences of those other dependencies.
-Phil
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
It needn't be zeroes -- a string of any other value would serve the cryptanalyst nearly as well.· Have you calculated just how rare that rare event is?·
It's exceedingly rare.· Reading ten characters of the message probably wouldn't avail him much, but in order for the ciphertext to contain ten characters of consecutive plaintext, there would have to be ten consecutive zeros in the keyfile.· That will happen just more than once in 1024 bytes of "independently random" key.· My keyfiles are 3 GB in length.· So it will occur in about one out of 4x1014 of my 3 GB keyfiles.· That's once in 400 trillion keyfiles, each of which will probably encrypt at least several thousand·plaintexts that I may wish to send over the Internet.· I have a greater chance to be killed by an impacting meteor tomorrow.
Engineering is the science of calculating what is sufficient.
I don't think I'm going to lie awake nights.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
Post Edited (Carl Hayes) : 4/11/2009 1:22:07 AM GMT
-Phil
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.
If the keyfile is random, and the encipherment is, say, a simple XOR, then the ciphertext will be equally random.· If not, not.
The cryptanalyst will examine the ciphertext to determine, among other things, in what ways it departs from randomness.· Any test you can perform to find strings to remove from the key, the cryptanalyst can perform on the ciphertext·to find out what kind of strings you removed.· The more you do of that kind of thing, the more the cryptanalyst can infer about your keyfiles.
In a random byte-oriented keyfile, 00 [noparse][[/noparse]hex] will be followed by 00 one time out of 256, and by 0000 one time out of 65536.· If you remove all strings of, say, three or more zeros, these 0000 strings will be less frequent than expected (when you remove 000000, you are removing two occurrences of 0000).· Since the character set of English doesn't use even half the 256 possible bytes, and isn't random at all, the ciphertext will contain hints of what you did.
If the keyfile is random (what Phil calls·independently random), it will contain, say, "000000" [noparse][[/noparse]hex] with a certain frequency [noparse][[/noparse]once in 65536 bytes].· If you remove them, then the ciphertext will contain fewer possible products of such a keystring than it would normally contain.· The digraph "th", for example,·is·very common in English.· If you remove all sequences of, say, three or more zeroes in the keyfile, there will be fewer·"0000" keysequences·than the 1/256 normally expected, and there will be fewer digraphs "th" than normally expected in the ciphertext.· So the cryptanalyst can figure out you did that, or something like that.· That is, if you look for those and remove them, the cryptanalyst will discover that you did so, and he can then assume that no part of the plaintext was enciphered with such a string.· So he will know more about·your keyfile, and·the relation between your plaintext and your ciphertext, than he would know if you did nothing.· For example, if he figures out that you took out all 0000 strings, he can assume that "th" in the ciphertext is never "th" in the plaintext.· He can make the same assumpion about every other digraph, too.
Why work so hard to help your opponent?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
Post Edited (Carl Hayes) : 4/11/2009 6:05:44 AM GMT
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net
Sorry cant remember what the software was called
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Need to make your prop design easier or secure? Get a PropMod has crystal, eeprom, and programing header in a 40 pin dip 0.7" pitch module with uSD reader, and RTC options.