Building an OTP Key Generator.

mctrivia

virtuPIC said...
If you want to produce reasonable, uniformly distributed real random numbers you should use a little external hardware which employs quantum effects. No, I don't mean a radioactive sample with Geiger counter. Would work - but would be rather expensive. But what else? You can simply take a diode or part of transistor give it a high backward voltage and measure the current. There will be noise that is real quantum-random.

My thinking is shield the random number generator to minimize any effects from outside noise. Keep only the least significant bit of he voltage across the resister.

Was thinking to use this AD; http://focus.ti.com/lit/ds/symlink/ads1225.pdf

would take almost a year though to generate a 2GB key file.





Outside of the randomness was thinking use a propeler and 2 uSD cards to store the key. uSD because it is smaller and easier to smugle.

Anyone know if I am on the right track and how acurate an ad convert would be needed? 200 days is to long to wait to generate the keys. 1 to 7 days would be good. 8-30 pushing it but ok.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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.

SRLM

Assuming that the basic design works (I have no idea about that), you could just use several simultaneously. Since each one is 'random' you can just take the random values as they come in. Make a 30 generator array and you'll get your files in no time.

mctrivia

that ad is $8 each. Paralleling the inputs is definitely an option but cheaper ad would need to be found. I went with 24 bit because I figure it would probably need to be pretty accurate to work. Maybe that is not needed though. Or maybe a much faster sample rate one could be found. Have not done to much research on what ad can be found because I am not sure what would be needed. This circuit falls outside of what I understand and know.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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.

MagIO2

Did I miss a breaking news in key cracking? Why would you need a 2 GIGABYTE key?

virtuPIC

MagIO2 said...
Did I miss a breaking news in key cracking? Why would you need a 2 GIGABYTE key?

Well, it's more breaking olds. Wikipedia is your friend.

In brief: There is only one incrackable cryptosystem. The one time pad. That's the OTP in the subject. Each bit is encrypted separately and no key will be recycled.To encrypt a single message bit you need one key bit. The key is as long the message.

To generate such a key sequence you need uncorrelated real random data of equal distribution over {0,1}. If an attacker gets a transmitted message and the key used for this transmission he cannot use it to crack any other transmission since there is a key change to a completely unrelated key.

mctrivia said...
Anyone know if I am on the right track and how acurate an ad convert would be needed? 200 days is to long to wait to generate the keys. 1 to 7 days would be good. 8-30 pushing it but ok.

As I already wrote in another thread, I would only use 1 bit ADC. I don't know how you call it - anyway, the shot through a bipolar junction is a binary quantum effect. Many of them happen and your lines and your ADC will low pass filter them. There is no need to care for several bits. However, the comparator implementing the 1 bit ADC should be sensitive enough to find the signal. I don't know whether the logic CMOS input fulfills this.

And regarding the speed: If you use a fast comparator (look at www.ti.com you can get the bits as fast as you can shift them.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys

heater

You might want to try a circuit like the one here www.cryogenius.com/hardware/rng/

Not sure if you will need the Schmitt trigger on the way into the Prop.

He seems to be getting 10,000 random bits per second or about 1Gb per day.

Don't forget to unbias the output, you may have more ones's than zeros or vice versa.

Like so "To unbias the bits, I use the Von Neumann method, described in the Schneier red book (Applied Cryptography 2nd Ed.) on page 425. I sample two bits and discard them if they are equal. If they are not equal, then I accumulate one of the bits. When enough bits are accumulated, I output them"

I'd be inclined to drive the transistors from a separate battery supply for isolation and shield battery and transistors together.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

pgbpsu

@mctrivia-

Here's a 2 channel ADC which will give you 24-bit samples at 96Khz. Last time we bought these they were ~$5 each. It may be more complicated than you want to deal with. It needs a clock whereas the one you posted didn't. However at nearly 100x the speed of the one you posted it, it might be worth it. We actually run these at 80Khz, which allows the PASM to read both channels in one cog. I can share some code for these if you are interested.

pgb

mctrivia

heater that is a great schematic. no ad required. as you said building 2 identical circuits and only keeping the bits from a when b is the opposite would help unbiased as well as cut down on any noise from background. I figure if each is separately shielded and the 12v is separately regulated each with separate regulator for prop.

to make sure noise is at a minimum on power I will use several 0.1uF caps near rails and a 12v supper cap after each regulator.

traces will be identical to both collectors

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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.

heater

I built that circuit some time ago, only got as far as connecting the output (no schmitt) to my PC sound in and listening to the fizz.

Actually the technique of sampling two bits was supposed to be two consecutive bits from one circuit. You should do a search for "Von Neumann method" to see what it is all about.

I can't quite convince myself that taking the two bits from two separate circuits is equivalent. Might be.

Hmm.. what if one circuit is in the middle of a long string of ones. Then every time the second circuit produces a 0 you would accept a bit because they are different. Doesn't seem quite right to me.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

mctrivia

for true random numbers 100 ones in a row will eventually happen. so if the key is to be truly random this should be allowed. obviously though this would make a poor key so some software intervention is needed to prevent. will still build 2. my way minimizes chance of noise then also double sample the way you ment. software will also have to process for week keys.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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 Pilgrim (PhiPi)

Interesting point. You really don't want complete independence. The simplest way to eliminate such runs would be to keep a FIFO of the last n groups of m bits (where m icould be 7 or 8 for ASCII characters). If a new m-bit value is in the FIFO, discard it, and pick another at random until you get one that's not in the FIFO.

Now the question is this: if an attacker knew what m and n were, would that be enough of a clue to get a handle on the OTP?

-Phil

mctrivia

would not want anything so organised as that. just something to stop long runs of same bit. a restriction of no more then 12 repatriation bits would not weeken otp but also not leave large chunks plain or just inverted.

for space reasons I would not use ascii but instead a variable bit length coding system. uses less space

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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.

heater

Not sure I'd worry about long runs so much, they are quite rare after all. If you do why not just XOR your message bytes with $AA or $55 first.

You should include a check for the total failure of your generator. For example in the circuit I posted if the 12v supply drops too low the randomness suddenly stops. I forget the threshold voltage I found with my transistors.

If you are using the Von Neumann method on successive bits from a single generator this is not a problem as there will then be no output, it will just be sitting there waiting for bits to change. Perhaps you would have a time out so that the user of the random bits is not waiting for ever but gets an error return.

If you are comparing two bits from two generators you would be in trouble if one is stuck 1 and the other is stuck 0. The un-biassing would always return the same 1 or 0.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

mctrivia

in ul safe cracking standards the person determining how long it takes to crack knows everything about the safe and assumes the thef would also.

the strength of encryption should be the same. we should assume the thef knows everything but the key and original message.

that said xor with static number would be useless. are only strength is in the quality of key we generate.

quality means true random with no cyclic repetition from things like 60hz hum or supper long repeating bits leaving essentially unencrypted. to many restrictions on random also weakens

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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.

heater

I totally agree. Scrap the XOR idea.

However, if you stick to the true randomness (and lets assume our generator is) then you have to accept the fact that long runs of ones or zeros can happen. Albeit rarely. Selecting from the incoming bits in any way, to remove long runs say, is breaking the rules.

Chip says we don't need any external circuitry to do this on the Propeller.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

mctrivia

chip real random works well but has no method to cancel potential cyclic noise. needs some testing

I will use the real random to generate a test file and upload to my server for people to analyze.

not worrying about pins because key generator and encryptor are not same device

yes stopping real long runs does remove combinations but my suggestion of 12 max only removes 2 in 8 billion

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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

woops 2 in 4096

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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

maybe 21 bits better. 1 in 2 million

using variables bit length character also adds security as you don't know where char starts without knowing from beginning. should be at least one 1 before a long run in any 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.

heater

I don't think you should worry. Let's say you just want to encrypt a regular ASCII text file, 1 byte, 8 bits per character. You'll need a run of 24 bits of zero's to leave 3 consecutive characters unchanged by the encryption. Looks like a 1 in 16 million chance. Are those three characters likely to be meaningful to anyone?

Whatever you do check out the Diehard random number tests stat.fsu.edu/pub/diehard/

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

mctrivia

probably not needed. Though I don't normally use ASCII. I have a few system I use. Here is one:

MCVBEET1(Matthew Cornelisse Variable Bit English Encoding Table 1)
0 10000000110
1 10000000000100
2 10000000000101
3 10000000000110
4 10000000000111
5 10000000000001
6 10000000001100
7 10000000001101
8 10000000001110
9 10000000001111
A 1011
B 000001
C 01001
D 10101
E 111
F 00010
G 100011
H 0110
I 1101
J 1000000111
K 1000001
L 10100
M 00001
N 1100
O 1001
P 100001
Q 1000000010
R 0101
S 0111
T 001
U 01000
V 000000
W 00011
X 1000000110
Y 100010
Z 1000000001
$ 10000000000010
% 10000000000011
, 100000001111
. 100000000010
space 100000010
shift 100000001110
caps 100000000000000001
Enter 100000000000001
End 1000000000000001
ASCII 10000000000000001
UNICODE 100000000000000000



To encode a message pick the bit pattern to the letter you want. Letters are lower case unless following a period.· shift preceding a symbol changes its normal state.· all are capitalized if between to cap symbols

To decode start at first bit and find bit patern in table that matches. remove that section and continue.


In general this table gives smaller file sizes then ASCII. Also because of the variable bit length property you can't just start decoding in the middle of a message making it more secure in an OTP like encryption.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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.

Post Edited (mctrivia) : 4/12/2009 8:27:46 PM GMT

Phil Pilgrim (PhiPi)

mctrivia said...
Also because of the variable bit length property you can't just start decoding in the middle of a message making it more secure in an OTP like encryption.

That doesn't really enhance the security. The longest bit pattern is 18 bits, which means that you could start decoding anywhere, then increment by one (no more than 18 times) until you got something that makes sense.

-Phil

virtuPIC

This talking about encoding brings me to another point: There is one option to increase security of a cipher: compress the data you want to encrypt as small as you can! If the someone attacks your ciphertext without knowing the plaintext they have to check if the tries give sensible paintext.

In ASCII seomething like 'wrnpois.nop indv' means that the key has not been found. If the attacker gets 'Hello, wolrd!' chances are high that the key has been found. In other terms, if your plaintext language has high redundancy then an attacker knows if an attempt gave a sensible decryption. If your plaintext language has no redundancy then all possible bit sequences are sensible and the attacker doesn't know if it was a success.

Compression reduces the redundancy. Most of the possible bit sequences are valid and sensible. If you have a few characters of English text in ASCII you only get very few sensible texts. But be aware that many compression programs add fixed headers that can be used to attack your cipher!

By the way, do you know the Q-codes? There have been abbreviations used at least in second world war to compress clear text. A few of them are still used - also in civilian context. For instance in aviation QNH is still used for something like 'pressure comverted to medium sea level in hPa' used for altimeter setting. Quite a compression factor. You know of Enigma? The German crypto engine cracked by a British group around Alan Turing? They did something unusual when observed to provoke transmission in clear text (read: without compression). Something like shooting seals (I mean the animals) lying on a beach...

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys

mctrivia

but starting in middle of string may look like real characters. just thinking of this encoding system deals with long runs of 0s better.

also longest symbol is 34 bit 18+16 bit unicode symbol

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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.

virtuPIC

'This encoding system' is MCVBEET1? Sure, this is a Huffmann-like compressed code! This increases security - but only a little since there is still a considerable amount of redundancy. And, what about transmission of data in certain formats like HTML or XML where you have lots of repetitions? Sure, here you could also introduce abbrevs but reasonable multi-char compression algos do it by themselves.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys

mctrivia

MCVBEET1 is indeed a hufman compression of the standard deviation of english writing.
meant for sending plain text messages. I would include a crc for error checking but if that is encrypted with otp it will not help an attacker.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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.

GreyBox Tim

OTP is regarded as the most secure key scheme, but it is also reliant on a key exchange once the key are all used up (which are inherently less-secure).

If you're really worried about the security of your data, don't use just one method (like only AES-128 only...).


Also:

• Pad the beginning of your data with random or pseudo-random garbage data to prevent duplicates of the plain-text before encryption (in a stream-type cipher), or the beginning of each block of data with PRNG data (for a block-type cipher). Sending the same plain-text twice with the same key (if the key was used twice by accident), will result in the same cipher text the second time...
• For text and ASCII files, try a DC balancing algorithm or scrambling method like what is used in Serial digital video (a polarity insensitive NRZI algorithm: G(x) = (x⁹ + x⁴ + 1)(x + 1) ) - before encryption (this makes it harder to determine when you've found the plain-text).
• For encryption, use keys which are digested by some form of hash first (not just MD5 or SHA-1/256/512 - use other hashes, many are available).
• When you encrypt, don't just use one pass of one type of encryption - use different encryption methods (like AES-256, Rabbit, HC-256, Salsa 20/12, Sosemanuk, Trivium, Grain, and Mickey), different keys each pass - and use the key digest to pick which algorithm is used for each of your steps (don't just do what they did with 3DES and use just one routine which is already broken, three times).
• Finally - even if you use published encryption standards to obscure your data, don't share how you implement them in your project with anyone (even your mom ). Everyone has a breaking point under the proper persuasion, everyone.

Take a look at polymorphic ciphers too...

-Tim


P.S. To your initial point, don't smuggle an SD card with a key... The best idea is to do some form of stenography (embed the key data in another file type (like the LSB of a large bitmap - with no encoding!!! STools does this but leaves a finger-print that investigators are already looking for). You can also place the key in a hidden partition on a drive for plausible-deniabillity... If you get caught with an SD card hidden in your shoe or something, you're more likely to be compelled to reveal the contents. If a key-file was hidden in a picture, that looked like every other picture that was in a folder (and wasn't something awful like kiddy-porn), in most cases even if you were asked to show the contents of a file folder on a thumb-drive, the investigator wouldn't likely have enough probable cause to look further at the files (this may not matter if you are on a watch list though). -T

Post Edited (GreyBox Tim) : 4/13/2009 6:03:34 AM GMT

mctrivia

physical delivery of key is the only safe way and since keys are gigs in size hiding in picture not to likely. besides usd can be broken easily if caught and can be hidden under your skin anywhere

not that I would go that far since legal here

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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.

virtuPIC

Yes, Huffman codes are optimal in single character compression. However, it leaves redundancy in character sequences. If you have a 'q' then chances are high that a 'u' will follow. I didn't know MXCBEET1 before so I can't tell about average character length. I still think that some compression working on character sequences like LZ77 and companions give better compression concluding in smaller data size and higher security.

BTW, are we running off topic here? What was the original question? The subject tells something about an OTP key generator...

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys

mctrivia

MXCBEET2 has qu as a single symbol. will see if I can find that one.

yes off topic but related

mctrivia

Tried using real random object(with wait time increased to 0.5ms).

I generated a 126MB file during my shift today.

I have attached the diehard results of this file. in what I see it looks pretty good. Actual file will be available here as soon as it is done uploading. Currently at 29% Will probably finish by the end of the next hour(7PM MDT)

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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.

Post Edited (mctrivia) : 4/18/2009 11:51:55 PM GMT

mctrivia

Only one that seems to have given bad results though any are near 1 or 0

OPERM5 test for file otp00000.bin
For a sample of 1,000,000 consecutive 5-tuples,
chisquare for 99 degrees of freedom= 72.793; p-value= .022276
OPERM5 test for file otp00000.bin
For a sample of 1,000,000 consecutive 5-tuples,
chisquare for 99 degrees of freedom= 81.191; p-value= .096333



upload of base data is now done.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
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.

Post Edited (mctrivia) : 4/19/2009 12:56:46 AM GMT