Use of simple schemes
in [Cryptography]
|
Prev: Merry Christmas 10
Next: test
From: Maaartin on 15 Nov 2009 17:29 On Nov 15, 9:39 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > > Maybe you can't recover the matrix, but surely you can learn a lot of > > about it. Using this information you can break the scheme if the PRNG > > is insecure. Take as an example a totaly stupid PRNG generating the > > sequence > > seed, seed+1, seed+2, ... > > and try yourself. > > Why should we make such an assumption? (One doesn't walk on the street > with a helmet just because some bolt possibly might fall down from > a helicopter flying over one's head, right?) We have nowadays, in > constrast to the time of classical crypto, good PRNGs like the recent > one by Marsaglia. So again: - Either the PRNG is perfect and you need nothing more than xor it with the plaintext. - Or it is not and you have no "alternative to applying sophisticated algorithms that require deep analysis in their design and much care in implementation" since you need it all. I proposed you to try with the extremelly stupid PRNG since using it the analysis is simple. You can take KISS or SuperKISS if you want, but than you must work harder. At the end you need either break it or give a good reason why breaking it is hard. Or at least show it to be more secure than simple xoring with the PRNG output. And first you need to specify all the details: How large should the matrix be, over what ring, how you ensure it to be regular, etc. You also need to state on what plattforms it works (do smart cards have enough power for it?), how to implement it efficiently, how to prevent timing attacks, etc.
From: Mok-Kong Shen on 15 Nov 2009 17:39 Maaartin wrote: > Mok-Kong Shen wrote: >>> Maybe you can't recover the matrix, but surely you can learn a lot of >>> about it. Using this information you can break the scheme if the PRNG >>> is insecure. Take as an example a totaly stupid PRNG generating the >>> sequence >>> seed, seed+1, seed+2, ... >>> and try yourself. >> Why should we make such an assumption? (One doesn't walk on the street >> with a helmet just because some bolt possibly might fall down from >> a helicopter flying over one's head, right?) We have nowadays, in >> constrast to the time of classical crypto, good PRNGs like the recent >> one by Marsaglia. > > So again: > - Either the PRNG is perfect and you need nothing more than xor it > with the plaintext. > - Or it is not and you have no "alternative to applying sophisticated > algorithms that require deep analysis in their design and much care in > implementation" since you need it all. > > I proposed you to try with the extremelly stupid PRNG since using it > the analysis is simple. You can take KISS or SuperKISS if you want, > but than you must work harder. At the end you need either break it or > give a good reason why breaking it is hard. Or at least show it to be > more secure than simple xoring with the PRNG output. > > And first you need to specify all the details: How large should the > matrix be, over what ring, how you ensure it to be regular, etc. You > also need to state on what plattforms it works (do smart cards have > enough power for it?), how to implement it efficiently, how to prevent > timing attacks, etc. Regarding "deep" analysis see my thread "Rendering prediction of congruential random number generators hard". Yes, researchers have done good analysis, but these could easily be defended. (compare also my second post in the thread "Dynamic change of encryption keys". However, please post direct comments to that post to that thread.) M. K. Shen
From: Unruh on 15 Nov 2009 19:07 Mok-Kong Shen <mok-kong.shen(a)t-online.de> writes: >Maaartin wrote: >> Mok-Kong Shen wrote: >>> Maaartin wrote: >>>> But having a fast perfectly secure PRNG you could simply xor it's >>>> output with the plaintext. Using an unsecure PRNG makes the Hill's >>>> scheme vulnarable again. And again, you need an expensive analysis of >>>> the cipher what is just what you wanted to avoid. >>> I don't yet understand your last sentence. If an n*n matrix is >>> used to process less than n^2 units (characters or computer words) >>> of text, there simply isn't possible to recover that matrix, if >>> the analyst has the plaintext and ciphertext available. Thus, >>> inferring the parameters of the PRNG would not be feasible in >>> my view. >> >> Maybe you can't recover the matrix, but surely you can learn a lot of >> about it. Using this information you can break the scheme if the PRNG >> is insecure. Take as an example a totaly stupid PRNG generating the >> sequence >> seed, seed+1, seed+2, ... >> and try yourself. >Why should we make such an assumption? (One doesn't walk on the street >with a helmet just because some bolt possibly might fall down from >a helicopter flying over one's head, right?) We have nowadays, in >constrast to the time of classical crypto, good PRNGs like the recent >one by Marsaglia. It is a logical procedure to demonstrate that your "proof" is wrong. Since it should, according to the stated assumptions, also apply to that silly PRNG, and since it clearly is wrong for the PRNG, your proof is wrong. Ie, proof by counterexample. If you make some statement about the integers which someone points out is wrong for the integer 5, your proof, or your assumptions are wrong. You may be able to repair the proof, but doing so by saying that it is valid for all integers except 5 is not convincing to anyone. >M. K. Shen
From: Mok-Kong Shen on 16 Nov 2009 04:10 Unruh wrote: > Mok-Kong Shen writes: > >> Maaartin wrote: >>> Mok-Kong Shen wrote: >>>> Maaartin wrote: >>>>> But having a fast perfectly secure PRNG you could simply xor it's >>>>> output with the plaintext. Using an unsecure PRNG makes the Hill's >>>>> scheme vulnarable again. And again, you need an expensive analysis of >>>>> the cipher what is just what you wanted to avoid. >>>> I don't yet understand your last sentence. If an n*n matrix is >>>> used to process less than n^2 units (characters or computer words) >>>> of text, there simply isn't possible to recover that matrix, if >>>> the analyst has the plaintext and ciphertext available. Thus, >>>> inferring the parameters of the PRNG would not be feasible in >>>> my view. >>> Maybe you can't recover the matrix, but surely you can learn a lot of >>> about it. Using this information you can break the scheme if the PRNG >>> is insecure. Take as an example a totaly stupid PRNG generating the >>> sequence >>> seed, seed+1, seed+2, ... >>> and try yourself. > >> Why should we make such an assumption? (One doesn't walk on the street >> with a helmet just because some bolt possibly might fall down from >> a helicopter flying over one's head, right?) We have nowadays, in >> constrast to the time of classical crypto, good PRNGs like the recent >> one by Marsaglia. > > It is a logical procedure to demonstrate that your "proof" is wrong. Since it > should, according to the stated assumptions, also apply to that silly PRNG, and > since it clearly is wrong for the PRNG, your proof is wrong. > Ie, proof by counterexample. If you make some statement about the integers which > someone points out is wrong for the integer 5, your proof, or your assumptions are > wrong. You may be able to repair the proof, but doing so by saying that it is > valid for all integers except 5 is not convincing to anyone. You ignored the other part of my post. Please make your argmentation more effective by posting 'direct' critiques to the stuff I posted in the other two threads mentioned: "Rendering prediction of congruential random number generators hard" and "Dynamic change of encryption keys". Thanks in advance, M. K. Shen
From: Mok-Kong Shen on 18 Nov 2009 04:40
Mok-Kong Shen wrote: > >> ...... as an alternative to applying sophisticated algorithms that >> require deep analysis in their design and much care in implementation, >> employ certain simple primitive procedures, using a much higher number >> of steps of operations to compensate for their inherent weakness with >> respect to the complex procedures underlying the sophisticated >> algorithms. A viable example of this in block encryption could be using sub-optimal S-boxes but additional rounds to compensate for the less than theoretically possible optimality, if for practical reasons (time, resources) one couldn't arrive at an "ideal" design of the the S-boxes. This is not suggesting that one could allow carelessness, blind simplifications, laziness, etc. in design but simply indicating the "reality" which as everywhere else in life forces one to be a realist to choose and accept an economically best optimum in practice and not be an idelist and behave pedantically to find the ideal but practically not achievable theoretical optimum. In fact, with the progress of computers many approximative/iterative procedures have come up to practically "replace" the exact solutions of a large number of computational problems. For example, while a century ago one painfully searched for exact solutions of differential equations (in terms of the known functions), nowadays differential equations are commonly solved on computers with iterative methods which were not practically doable without today's computing power. Genetic algorithms, neural networks, simulation methods etc. etc. wouldn't have come into being at all, if one hadn't relatively cheap computing power at one's disposal. M. K. Shen |