Encrypting odd sized buffers
in [Cryptography]
|
From: Paul Rubin on 24 Jun 2010 02:09 Ross MacGregor <ross__macgregor(a)hotmail.com> writes: > Yes, randomness is what I am seeking. I am actually trying to build a > non-repeating PRNG to fit a 108 bit number space. Also, to point out the obvious, if you only need a few million numbers, you could generate them randomly, and then check for duplicates if you're that worried about them. It's a safe bet that you won't find any though. Are these keys for a WEP implementation or something like that? (The only application where 108 bits and uniqueness requirements immediately come to mind). Having internal state in your device that allows reconstruction of old keys is probably a worse security risk than the very low chance of getting a duplicate from purely random generation.
From: Mok-Kong Shen on 24 Jun 2010 02:14 Ross MacGregor: > > Mok-Kong Shen wrote: >> [Addendum] I meant that the wordings of your previous posts leave open >> a (IMHO at least 'minutely') possible interpretation that security might >> not be a requirement for you and what you seek was only randomness, in >> which case the solution would have been rather simple. > Yes, randomness is what I am seeking. I am actually trying to build a > non-repeating PRNG to fit a 108 bit number space. If randomness is the only requirement, then the more complicated schemes discussed by several experts of the group are not necessary for you. I'll suggest that you employ permutation polynomials mod 2^108, since this is very simple to use. If f(x) is such a polynomial, then f(x) for x=0..2^108 gives a permutation that exactly meets what you requre. In the thread "A C-code for permutation polynomials mod 2^n" of 21.03.2010 you'll find in the comments the criteria of the coefficients of f(x) that are to be satisfied for it to be a permutation polynomial in general (there the reference to a paper by R. Rivest). You can arbitrarily randomly choose an f(x) that satisfies the criteria. The code I gave implements the more restricted case where recursive computation starting from x_0 according to x_(i+1) = f(x_i) generates a full-cycle permutation (there the reference to V. Anashin and A. Khrennikov). But I think that even this is likely to be 'general' enough for your use, in which case you could use my code straightaway. Note that, as remarked in the comments there, you could use the function 'invpermpoly' to invert the mapping, even if you choose to use the more general f(x). The issue of randomness of the result is beyond my poor math knowledge to discuss theoretically. I have though done some limited experiments with f(x) satisfying the more restricted criteria and found that the outcome satisfactorily passed Maurer's Universal Test. M. K. Shen
From: Mok-Kong Shen on 24 Jun 2010 02:22 Mok-Kong Shen wrote: > x=0..2^108 .... Typo. Please read x=0..2^108-1. M. K. Shen
From: Ross MacGregor on 24 Jun 2010 02:24 unruh wrote: > Ie after you have issued a billion numbers, the probability of repeats > is far less than the probablility that civilization will be destroyed by > an asteroid strike in the next year. Is that a sufficeintly "strong > guarentee" It is certainly far far far far less than the probablility > that your company will go out of business or that eveyone in management > will be killed at once due to some accident. I hear you, but I need to factor human behavior into this equation. For most people a chance of something happening means that it WILL happen. We don't understand big numbers all that well. This code will be audited by third-party to ensure it passes the regulations and requirements. Depending on who these people are and what kind of day they are having we could get rejected because because the PRNG does not guarantee unique cycle of numbers.
From: Paul Rubin on 24 Jun 2010 02:40
Ross MacGregor <ross__macgregor(a)hotmail.com> writes: > This code will be audited by third-party to ensure it passes the > regulations and requirements. Depending on who these people are and > what kind of day they are having we could get rejected because because > the PRNG does not guarantee unique cycle of numbers. Who is going to do your audit? If I were doing it (and I have done them in the past), I'd be more concerned about contortions intending to guarantee uniqueness but that instead ended up creating more opportunities for errors. Have you read the book "Practical Cryptography" by Schneier and Ferguson? It has a reasonable amount of advice about issues like this. Also "Security Engineering" by Ross Anderson. More to the point, you should probably get actual cryptographers involved in your design. |