A poorman's block encryption algorithm
in [Cryptography]
|
From: Maaartin on 12 Mar 2010 12:48 On Mar 12, 6:24 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Maaartin wrote: > > There's a problem with polynomials you was already told about: They > > propagate only towards higher bits (unless you use non-power of two > > modulus which is slow). So you can be sure, that a couple of least > > significant bits can be found out easily, no matter how many rounds > > you do. Starting from them, higher bit can be found, etc. I already > > recomennded a remedy, so use it or find another. > > Extremely sorry for my poor memory. Could you kindly sketch your remedy > once again or provide a pointer? Concerning predictability of > congruential PRNGs, I previously suggested to use (pseudo-random) > cyclic shift of bits in computer words of the output as a counter- > measure. That could also be done in the present context. I can't find the link anymore, but it was very simple: Using something like rotate(p(x), distance) or p(x) ^ (p(x) >> distance) or p(x) + (p(x) >> distance) with 0<distance && distance<32 propagates the higher order bits to the lower order bits, Fixed distance makes it easier to analyse, while variable distance makes the lowest 5 bits to influence the result in quite an "unpredictable" way. For an algorithm using both fixed and variable rotations and multiplication see http://en.wikipedia.org/wiki/RC6
From: Greg Rose on 12 Mar 2010 15:47 In article <hndosi$b1a$02$1(a)news.t-online.com>, Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote: >rossum wrote: > >> If you are prepared to move away from block cyphers to a stream cypher >> then RC4 is easily memorisable and programmable from memory. It is >> not perfectly secure but is certainly easily memorized. > >If I don't err, stream ciphers have difficulties in issues of >authentication. That's why I considered block encryption. (Note in this >respect that the scheme depicted allows large block sizes.) Block ciphers also have difficulties in issues of authentication. Don't listen to M-K. If you need message integrity, get it from a message integrity primitive (which may, or may not, be based on a block cipher). Greg. --
From: Mok-Kong Shen on 12 Mar 2010 16:18 Maaartin wrote: > Mok-Kong Shen wrote: >> Extremely sorry for my poor memory. Could you kindly sketch your remedy >> once again or provide a pointer? Concerning predictability of >> congruential PRNGs, I previously suggested to use (pseudo-random) >> cyclic shift of bits in computer words of the output as a counter- >> measure. That could also be done in the present context. > > I can't find the link anymore, but it was very simple: Using something > like > rotate(p(x), distance) > or > p(x) ^ (p(x)>> distance) > or > p(x) + (p(x)>> distance) > with 0<distance&& distance<32 propagates the higher order bits to the > lower order bits, Fixed distance makes it easier to analyse, while > variable distance makes the lowest 5 bits to influence the result in > quite an "unpredictable" way. > > For an algorithm using both fixed and variable rotations and > multiplication see > http://en.wikipedia.org/wiki/RC6 I suppose that in the context of outputs of congruential PRNGs, it suffices to do the conceivably simplest scheme as follows: One uses one output to provide 5 shift amounts (5*8=30<32) to cyclicly shift the following 5 outputs from the PRNG, etc. Since these shift amounts are pseudo-random, i.e. variable�, the analyst can't know where are the lower and where are the higher order bits of the original outputs from the PRNG and hence the sort of attacks of Boyar et al. would fail to work. Thanks. M. K. Shen
From: Mok-Kong Shen on 12 Mar 2010 16:31 Greg Rose wrote: > Mok-Kong Shen wrote: >> rossum wrote: >> >>> If you are prepared to move away from block cyphers to a stream cypher >>> then RC4 is easily memorisable and programmable from memory. It is >>> not perfectly secure but is certainly easily memorized. >> >> If I don't err, stream ciphers have difficulties in issues of >> authentication. That's why I considered block encryption. (Note in this >> respect that the scheme depicted allows large block sizes.) > > Block ciphers also have difficulties in issues > of authentication. Don't listen to M-K. > > If you need message integrity, get it from a message > integrity primitive (which may, or may not, be based > on a block cipher). That nothing in crypto "pratice" can be "perfect" is trivial. Thus certainly "block ciphers also have difficulties in issues of authentication". (Did I ever claim anything against that???) My point was, to fomulate stronger, that there is no authentication scheme based on a (strict) stream cipher at all (to my humble knowledge). Or are you of different opinion? On the other hand, I myself recently proposed an authentication scheme that, compared to one known scheme, has the advantage of using one key instead of two and with a chaining value that is unknown to the analyst. Comments and critiques to that would be very appreciated. M. K. Shen
From: Mok-Kong Shen on 12 Mar 2010 16:39
[Addendum] In the present context, one could advantageously employ what I mentioned in the thread "Introducing dynamics into block encryptions" as the third example of "inner" dynamics, namely to permute and/or cyclicly bit-shift the computer words of the input and/or output of a block depending on certain values taken during the processing of a preceding block. M. K. Shen |