Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

The simplest way to generate truly random numbers for OTP keys is to measure the time in milliseconds between each keystroke on a keyboard. The randomness depends on the user typing in various speeds. I coded an algorithm TRNG-Kms and did exactly that.

The questions are: How secure is this method for generating one-time pads in block- or stream-ciphers? Can certain random outputs be further predicted or even reconstructed by an attacker?

For that I'm adding some output samples here for cryptanalysis and level of randomness, sorted from worst to best. By testing the TRNG I have already observed some predictable patterns and some truly unpredictable ones, depending on the speed and style of typing text. The keyboard used here is a modern USB.

Output 1 : Typing a single letter / holding a single key
54,244, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33

This first output of numbers looks self-explanatory and is pretty much useless for OTP ofcourse, because the numbers are not random and can be reconstructed very easily. When holding a single key it takes exactly 33 milliseconds between each character before written on screen in this case. Except the first two numbers which display some randomness and result due to a hardware time delay or lag once you start holding down a single key. I'm not sure but I think all keyboards behave like this at the beggining. So the first of the two numbers varies a bit, the second one is always the same time value.

Output 2 : Typing two letters alternately with irregular speed
96,143,111,127,112,143, 96,128, 95, 96, 80,111, 79,111, 95,127

There is some randomness in this output, but many numbers are repeated 2-3 times in this short block. The number pair 96,143 seems to swap itself to 143,96 which can be explained by my two fingers pressing the two characters alternately on the keyboard. So this represents a rather weak one-time pad, not suitable for tough encryption since it may be broken very easily by an attacker with trying repeating numbers and swapping number pairs.

Output 3 : Typing random characters very fast, almost instantly
63, 64, 0, 0, 32, 32, 48, 32, 0, 15, 64, 0, 64, 0, 31, 31

That output speaks for itself. Except the random numbers, marked in bold, same numbers repeat and even form pairs. Most of these kind of outputs will produced the number 0, since the pressing time was so fast that a single keystroke took less than a millisecond. Not suitable for OTP keys.

Ok, here come better outputs and some may surprise you...

Output 4 : Typing the word "password" with normal speed and irregularity
227,143,255,160, 65,144, 96,175
big,sml,big,sml,sml,big,sml,big

Now this output looks pretty good at a first glance. The numbers appear truly random and there is no repition of any number in this very short block. However, when analyzing the numbers in detail there is a visible pattern: The first number is big, followed by a smaller number (227,143). Then once again (255,160). And after that the pattern switches. The next 2 number pairs are stored in the opposite fashion: small number followed by bigger number. This actually represents an attack vector in cryptanalysis by which an attacker could derive the key by applying exactly that pattern on the ciphertext which had been encrypted with that kind of OTP block. Even if the attacker doesn't know the random numbers he could guess any random numbers and lay them out in that particular pattern to arrive at some logic plaintext. So that output looks externaly good but is internaly flawed for OTP encryption.

Output 5 : Typing a random word with irregular speed
251, 16,242, 32, 66, 2,163,185
big,sml,big,sml,big,sml,sml,big

Same as Output 4. Numbers are random and no repitition. But a similar pattern: a big number is usually followed by a smaller number, except the last pair of numbers whose pattern is switched.

Output 6 : Typing very slowly with irregular speeds
(Raw) 121,215, 15,119,616,200,912,776,736,591,512,136,911,991,151,672
(Out) 121,215, 15,119,106,200,147, 11,226, 81, 2,136,146,226,151,162
(Pat) sml,big,sml,big,sml,big,big,sml,big,sml,sml,big,sml,big,sml,big

Now this output is different. Since I typed very slowly some of the resulting numbers are above 255 milliseconds which is outside the possible single byte range 0..255, so I have to make my TRNG crunch down the huge numbers to fit in the standard byte range again.
I'm doing this by subtracting the huge numbers with x = x - 255 until x is a rest value between 1..255.
For example, take the huge number 911 in the raw output and subtract 3 times the value 255 and the result is 146 in the final output.
I'd like to mention here that there may be other or even better methods to crunch down huge values of milliseconds into the byte number range 1..255, so they don't overflow. But I find my method sufficient enough and it creates additional randomness of numbers imo.
Despite all randomness of numbers, however, there is a visible pattern again: (3-2-3) 3 pairs of small numbers followed by bigger numbers, 2 pairs of big numbers followed by smaller numbers, and another 3 pairs of small numbers followed by bigger numbers.
I don't know what causes this pattern. Perhaps it is me and my style of typing on the keyboard. I have no idea.

Last but not least, my final and best sample output of TRNG-Kms so far. It's a 64 bytes length (512-bit) OTP block.

Output 7 : Typing a text with normal speed and unconscious irregularity
101, 80, 96,112,239,255,111,192, 95, 64,223,223,159, 95,225, 34
210, 79,143,224, 96,128, 66, 47,159,208, 64,144, 80,207,239, 63
127,162,177, 80,130, 17,112, 81, 10,113,129,143, 64,209,131,209
64,127, 79,202, 79,176, 49, 63, 49, 1, 96,224, 96,112,159, 63

Numbers which appear up to 3 times are marked as bold. Although in this longer block it does not hurt since random numbers are unique for the most part. Thus low repititions of numbers. And the pattern of big and small numbers in the number pairs appears more irregular too.

In conclusion, generating truly random numbers from milliseconds between each keystroke only works in some cases when the user types longer texts and does it with variant speeds, but not forced, but rather in an unconscious fashion.


EDIT

I'd like to continue this topic and ask further questions concerning cryptanalysis and security. But before I do so let me clarify some misconceptions which arrived in some comments...

There are 2 main classes of RNGs (Random Number Generators): Deterministic and Non-Deterministic.

Deterministic RNGs are:
PRNG (Pseudo Random Number Generator)
CSPRNG (Cryptographically Secure Pseudo Random Number Generator)

Non-Deterministic RNGs are:
CSRNG (Cryptographically Secure Random Number Generator), not to be confused with CSPRNG!
TRNG (True Random Number Generator)

The unique thing about TRNGs is that they are not required to work with seeds or random IV (Initialisation Vectors)! A TRNG usually produces an infinite stream of random numbers (bits or bytes for that matter) which are generated not by software but by some outside random source.

The outside random source can be anything from radioactive decay, atmospheric noise, white, brown or pink noise from a TV set, static interference from hardware components (such as USB or computer chips) or in the simplest way from keystrokes pressed by a human source, as I have presented here. The same can be done with mouse movements to generate truly non-determinstic numbers. "Non-deterministic" means truly random! And it does not require seeds or other intialisation vectors.

Now it may be argued, as one commentator implied here, that getting a stream of random numbers by simply reading the time between keystrokes and using that time as numbers does not really produce random / non-determinstic outputs. And this is exactly the reason why I started this question topic, because I'd like to experiment with this and find out if this is really the case or not.

So the new questions are:

  1. Is generating time-based numbers between human-made keystrokes really a non-deterministic technique which proves true randomness or not?
  2. How to improve the random number outputs, which consist of values representing milliseconds between keystrokes, in such a way that there are no underlying patterns in them anymore?

I hope someone can help answering these questions...

share|improve this question
    
    
@Ricky Demer Thanks for those pdf files. I appreciate that. But what am I supposed to do with those papers, besides reading them? In other words, is there anyhthing in those papers that may help me improve my TRNG? Can you point me to specifics? –  xorcoder Jul 26 at 20:32
    
er, I guess the last of those papers isn't actually helpful, since your data probably doesn't have that much entropy. $\:$ I would recommend using one of the middle paper's algorithms, since it seems likely to me that randomish key-presses would behave as a small-space source. $\;\;\;\;$ –  Ricky Demer Jul 26 at 20:45
    
@Ricky Demer I see. Decomposition of the small-space sources into more independent sources in order to create a higher entropy in the end. I will definately read that part. Thanks. –  xorcoder Jul 26 at 22:14
    
I would first eliminate repeating timings that are the same in case a user held down the same key for a long time. Then I would use a hash (e.g. Keccak) as a randomness extractor to get a more uniform distribution. For the low end you could assume each collected timing number has 1 bit of entropy, at the high end maybe 1 byte of entropy. For every 256 bits of estimated entropy, run them through the Keccak-256 hash and the digest is 256 bits of usable key material. Concatenate all the digests together. I wouldn't rely on key strokes alone, there are other physical inputs you can include too. –  NDF1 Jul 28 at 2:08

1 Answer 1

On your earlier questions:

1) How secure is this method for generating one-time pads in block- or stream-ciphers?

This method in itself is not secure, as the output weakly random entropy source, not a TRNG; there is entropy in the keystrokes, but without any whitening and extraction taking place, the output is - for instance - not well distributed. The methods you deploy may be a good start for estimating the amount of entropy in the results, but entropy does not equal randomness.

You should forget about the notion of an OTP in normal use; an OTP should be used as theoretical construct only, not something you use in practice. There is no OTP in block or stream ciphers.

Can certain random outputs be further predicted or even reconstructed by an attacker?

Yes, probably, as humans typing are not a very strong source of randomness, even if they cannot be observed. If they can be observed then all bets are off, of course. Milliseconds resolution is not very high either.


On the new questions:

1) Is generating time-based numbers between human-made keystrokes really a non-deterministic technique which proves true randomness or not?

No because it doesn't generate well distributed random values, it generates values with a certain amount of entropy in them.

2) How to improve the random number outputs, which consist of values representing milliseconds between keystrokes, in such a way that there are no underlying patterns in them anymore?

A hash based CSPRNG could be used if a full entropy source is not required.

Note that if you want to have a full entropy source, you should feed your data into a Randomness extractor. One method is to simply hash the output of your entropy data. Note that the amount of entropy in the data should then be twice the output of the hash function. Repeat this if you require more data.

Alternative it is possible to use any other extractor method described in NIST SP 800-90B, chapter 6.4, but those alternatives are more complex than simply hashing the output.

share|improve this answer
1  
That's a good idea using the values of milliseconds as seed inputs for a seed-based random number generator. However, I disagree with you that it should be a PRNG since any Pseudo Random Number Generator is not truly random but deterministic. In case of keystrokes randomly pressed by the user, I think it is less predictable than any PRNG / seed-based RNG imho, hence it falls into the category of TRNGs. I agree however that the milliseconds alone are not enough as input, because of the entropy, and should be further processed by a second layer of random input which obfuscates the first layer. –  xorcoder Jul 26 at 18:20
3  
Cryptography is non-negotiable, and won't be altered by belief. –  owlstead Jul 26 at 18:29
1  
First of all, this is neither a negotiation nor a belief nor an argument. At least not on my part. You suggested to use the TRNG output additionally with a PRNG. And I replied to you that adding a second random number generator may increase security, but it shouldn't be done with a pseudo random number generator (PRNG), because as every skilled crypto developer (me included) out there knows, PRNGs are deterministic and cryptographically not secure. That's why people use CSRNGs and TRNGs these days. So I don't know where you got that notion that a PRNG would increase any security. It does not. –  xorcoder Jul 26 at 19:47
1  
CSPRNG is a subclass of PRNG and was of course implied. To state in general that PRNG's are not considered secure is of course bunk. Maybe you should also read Dealing with Bias although I think that that Wikipedia page is not of a very high standard. Note that adding a second layer will not create a well distributed output (by itself); your output would still not be a good fit for a symmetric key let alone an OTP. –  owlstead Jul 26 at 19:56
    
@xorcoder : $\;\;\;$ His previous comment does say that "CSPRNG is a subclass $\hspace{1.74 in}$ of PRNG and was of course implied.". $\;\;\;\;\;\;\;$ –  Ricky Demer Jul 26 at 22:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.