Cryptography-Digest Digest #550, Volume #9 Fri, 14 May 99 14:13:03 EDT
Contents:
Re: Hello I am paper, please read me. (Bryan Olson)
Re: Hello I am paper, please read me. ([EMAIL PROTECTED])
Re: Hello I am paper, please read me. (Gustaf Dellkrantz)
Re: Hello I am paper, please read me. ([EMAIL PROTECTED])
Strength of PGP 1.0 conventional block cipher? (David Crick)
Re: Lemming and Lemur: New Block and Stream Cipher ("Craig Clapp")
Re: Crypto export limits ruled unconstitutional (Mok-Kong Shen)
Re: RSA-modulus binary decomposition (Alan Braggins)
Re: Hello I am paper, please read me. (Jim Felling)
Re: Review of "Cryptonomicon" (Tim Maurer)
WELCOM'99 Submission extended to May 29 (Uwe WILHELM)
Re: Thought question: why do public ciphers use only simple ops like shift and
XOR? (Christopher)
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Hello I am paper, please read me.
Date: Thu, 13 May 1999 22:24:34 -0700
[EMAIL PROTECTED] wrote:
>
> Sorry if the title is mean, but what's up?
>
> I wrote the paper on TwoDeck, and nobody even comments on it... That's
> because I am a newbie right?
It's because the volume of material you post is overwhelming.
Look at the decks after 8 or 16 shuffles. It seems the reason
for the non-randomness is that if x and y are n apart before a
shuffle, there's a very good chance they'll be 2n % 256 apart
after the shuffle.
--Bryan
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hello I am paper, please read me.
Date: Fri, 14 May 1999 07:37:33 GMT
> Look at the decks after 8 or 16 shuffles. It seems the reason
> for the non-randomness is that if x and y are n apart before a
> shuffle, there's a very good chance they'll be 2n % 256 apart
> after the shuffle.
So if you know the shuffling bisectors for all t shuffles (summed into
n) you can predict the original starting points? Hmm, not good.
Is this exploitable if you don't know the shuffling bisectors?
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: Gustaf Dellkrantz <[EMAIL PROTECTED]>
Subject: Re: Hello I am paper, please read me.
Date: Fri, 14 May 1999 08:32:29 GMT
In article <7hd3mo$3ba$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> I wrote:
> > There is yet another weakness that might improve your attack. The
> > problem is in the shuffle function and allows us to recover the
> > shuffle
> > value used when shuffling deck_A after a round of encryption.
> >
>
> That's saying you can isolate the deck_A from it's possible solutions.
>
> > Of N possible shuffle values N-2 move all cards of the deck except
> one.
>
> Um, no. All N values will create at one new deck from the old one.
> Where do you find this? Maybe it's true, I just don't understand.
An example shows what I mean. (This assumes I have interpreted the
shuffle function correctly :) The example is using N=8 and the starting
deck A = {0, 1, 2, 3, 4, 5, 6, 7}. Now we'll shuffle it with some
different values.
0 -> 0, 4, 1, 5, 2, 6, 3, 7 (A[0] & A[7] stays)
1 -> 1, 5, 2, 6, 3, 7, 4, 0 (A[2] stays)
2 -> 2, 6, 3, 7, 4, 0, 5, 1 (A[4] stays)
3 -> 3, 7, 4, 0, 5, 1, 6, 2 (A[6] stays)
4 -> 4, 0, 5, 1, 6, 2, 7, 3 (none)
5 -> 5, 1, 6, 2, 7, 3, 0, 4 (A[1] stays)
6 -> 6, 2, 7, 3, 0, 4, 1, 5 (A[3] stays)
7 -> 7, 3, 0, 4, 1, 5, 2, 6 (A[5] stays)
If you look at this you see that when shuffle=0, the first and last
value stay the same. When shuffle=4 no value stay the same and in all
other cases one value stays the same.
This means that if (for example) shuffle=0 the first value you pick out
of deck_A is the same as the first value that was picked out of deck_A
in the run before the shuffle. This also means that the first value that
is picked out of deck_B (indexed by A[0]) is the same as the first value
picked out of deck_B in the run before the shuffle. The first output
byte of this block is therefore equal to the first output byte of the
previous block and this can only happen when shuffle=0. This property
holds for all shuffle values as can be seen from the table above.
This allows us to get the shuffle value by looking at two consecutive
outputs and comparing them. This is easy assuming known/chosen
plaintext.
> > This might allow us to break the PRNG used to generate shuffle
> > values for shuffling deck_A.
>
> If you know the deck_A. Your attack requires isolating deck_A
> from 'N! / 2' valid solutions.
I don't need to know the contents of deck_A, just that some value stayed
in place when shuffling. And then I can detect which value stayed (which
position in deck_A holds the same value) and get the shuffle value from
that.
/Gustaf
--
Gustaf Dellkrantz ([EMAIL PROTECTED])
My opinions only and so on...
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hello I am paper, please read me.
Date: Fri, 14 May 1999 10:44:02 GMT
<snip>
Hmm, obviously the shuffle algorithm is no good. However I don't
believe you can exploit this easily.
Anybody have any good shuffle algorithms? Possibly fast too. I will
see what I can come up with.
Tom
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
Date: Fri, 14 May 1999 08:56:44 +0100
From: David Crick <[EMAIL PROTECTED]>
Subject: Strength of PGP 1.0 conventional block cipher?
Well I now have possesion of something which calls itself PGP 1.0 :)
Public key length options are 286, 510 or 990 bits, hashing is MD4,
compression is LZHuf and conventional encryption is an enhancement
of "Charles Merritt's algorithm".
I just wondered how secure the latter is ~8 years on. Has it held
up, or is it an interesting exercise for budding cryptologists?
Details from the docs:
For the cryptographically curious, PGP's conventional block cipher
has a 256-byte block size for the plaintext and the ciphertext. It
also uses a key size of up to 256 bytes. Permutation and substitution
are used on all the bits throughout the block in each round, rapidly
building intersymbol dependance between the ciphertext and both the
plaintext and the key. It can be configured to run from 1 to 8
rounds. It compares well with software implementations of the DES in
speed. Like the DES, it can be used in cipher feedback (CFB) and
cipher block chaining (CBC) modes. PGP uses it in CFB mode.
PGP's conventional encryption algorithm is based in large part on
cryptographer Charles Merritt's algorithms. Merritt's algorithm does
have something of a track record; derivatives of it have been used
for secure U.S. military communications. Merritt's original designs
were refined by Zhahai Stewart and myself to improve security and to
improve performance in a portable C implementation. The algorithm
has not yet (in 1991) been through a formal security review and has
had only limited peer review. It has been carefully scrutinized for
weaknesses. A full discussion of the architecture is beyond the
scope of this preliminary draft of this document. Interested parties
can get design details from me or from the published source code.
--
+-------------------------------------------------------------------+
| David Crick [EMAIL PROTECTED] http://members.tripod.com/~vidcad/ |
| Damon Hill WC96 Tribute: http://www.geocities.com/MotorCity/4236/ |
| M. Brundle Quotes: http://members.tripod.com/~vidcad/martin_b.htm |
| PGP Public Keys: 2048-bit RSA: 0x22D5C7A9 4096-DH/DSS: 0x87C46DE1 |
+-------------------------------------------------------------------+
------------------------------
From: "Craig Clapp" <[EMAIL PROTECTED]>
Subject: Re: Lemming and Lemur: New Block and Stream Cipher
Date: Fri, 14 May 1999 09:22:59 -0400
[EMAIL PROTECTED] wrote in message <7hh0bd$ugq$[EMAIL PROTECTED]>...
>On the Pentium without MMX, it's faster to not use any shifts or
>rotates of the block at all. The loop is repeated a number of
>times that is a multiple of the number of bytes in the block, so
>it is equivalent to:
>
> for (i=0; i<32; i++)
> block ^= rot(i,key[block[i]]);
>
>where rot(i,k) rotates k by 8*i bits in the opposite direction
>as rotate(), moving k[i] to k[0].
>
>If the rotations of the key are precomputed, then there is no
>need for any runtime shifts or rotates at all. On a Pentium
>without MMX, the block is stored in 4 32-bit registers, so the
>line inside the loop becomes 4 XORs. There are only 4 bytes
>in a 32-bit register, so it is only necessary to precompute 4
>different rotations of the key rather than all 32. This means
>that the key expands from 4KB to 16KB. I coded this on a
>Pentium II that had 32KB of cache, so the precomputed, rotated
>copies of the key could all fit within cache.
>
I had myself observed that the rotations of the key could be pre-computed,
but had discounted this due to having anticipated needing 16 different
rotations which would have used an unreasonable amount of cache
for tables. Your use of just four tables is a neat trick to keep the table
size manageable. I appreciate the elegance.
The ability to perform the XOR between the block and the key and let
the permuted byte appear in any position is a very nice feature of
your key construction (i.e. the aspect of XORing the address with the
permutation), and is something that can't be done with the table
construction used in WAKE without an additional operation to clear
the byte lane in which the key's permutation appears (which for
WAKE is done by right shift). Regardless of the fate of Lemming
and Lemur I suggest that others note this ingenious construction for
its potential for further uses as an invertible S-box.
>To extract the byte block[i], in 1/4 of the cases you just
>AND a copy of a register with FF, in 1/4 of the cases you
>shift a copy of a register by 24 bits, and in 1/2 the cases
>you must both shift and AND. These shifts are only applied
>to a copy of one register, not the whole block. There's no
>need to ever shift or rotate the entire block.
>
In case you are writing Pentium assembler then you can also
get access to the next to least-significant-byte in just one
operation by using the movzx instruction (e.g. movzx edx,ch).
This may or may not help and seems to be mostly at the whim
of the PentiumII's out-of-order execution unit into which there
is precious little visibility.
>I used these ideas when I did the timing tests on Lemming,
>which is why I said it encrypts at 19 cycles per byte.
>
>
>LCB
>
I note on another thread that attention has been drawn to Slide Attacks,
and also to concerns of 32-rounds being insufficient. I'm pleased to
note that your efficiency tricks only restrict the number of rounds to
be a multiple of four rather than the rather coarse sixteen as might be
interpreted from your earlier comments, but I'm sure you already
realized this.
Good luck.
- Craig
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Crypto export limits ruled unconstitutional
Date: Fri, 14 May 1999 15:50:05 +0200
Mike Eisler wrote:
>
> It is non trival to incorporate crypto into complex systems which
> have a primary purpsoe other than crypto.
>
> >because of provision of good user interfaces. For a commercial
> >product certainly one has to invest a sizable amount of resources.
> >But at least for a 'lean' version that is not required to have optimal
> >speed performance and user comfort, the implementation of the known
> >crypto algorithms can't be a very big thing. There are plenty of much
> >more complex jobs in software engineering that get done all over
> >the world.
>
> Fine, then show me the ubiquitous encryption in each of those jobs.
> I'd love to be wrong.
As I said, if user comfort is not an issue, then things become
simple. Just use a program implementing any chosen algorithm in the
'minimal' way, i.e. with no add-on features, transforming an ASCII
textfile of fixed record length into a HEX file of fixed record
length. Such output files can be processed by any software, popular
or not, that accept texts, including, in particular, e-mailer.
M. K. Shen
http://www.stud.uni-muenchen.de/~mok-kong.shen/ (Updated: 12 Apr 99)
------------------------------
From: Alan Braggins <[EMAIL PROTECTED]>
Subject: Re: RSA-modulus binary decomposition
Date: 14 May 1999 15:03:40 +0100
"Ulrich Kuehn" <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] writes:
> > Let m=37=5*B be an RSA modulus. Factors 5 and B (11 dec.) should be
> > found.
>
> You might want to check your math again. 37 is prime, so it cannot
> equal 5*11, which is 55.
37 hex is 55 decimal. 5*B hex is 5*11 decimal. So 5*B is 37.
------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Hello I am paper, please read me.
Date: Fri, 14 May 1999 11:27:32 -0500
You don't need to deduce A or B to break the code if you can deduce B(A(i))
for the interval i={kn+1,(k+1)n} then you have a break as the only thing
shuffling A will do is change the order in which those values are presented
in a predictable manner. One the keystream for any such interval is known
the keystream in the neighboring intervals is very similar to that
keystream and can be very effectively broken by a competent analyst.
Similarly for their neighbors, and so on.
What you have here is a fairly basic variant of a rotor cypher. Study the
techniques that were used in breaking those cyphers and then you could try
to make improvements. Another area to study is group theory.
Potential improvements include
1)Shuffling before a full deck is used.(i.e. after r letters are generated)
-- this will avoid exposing the whole structure of B(A(i))
2) Shuffling both decks -- preferably not in sync with each other.(this
prevents exposing a full deck to analysis before it is reordered)
3) Better Shuffles( perhaps a triple shuffle, or a shuffle and cut)
4)More decks.(Lengthens the period, requires more data to break)
5) Different sizes to A and B(as above, esp if the sizes are relatively
prime to each other)
6) Using other operations
7) Stuff not mentioned here -- I can't have thought of all possible
improvements.
[EMAIL PROTECTED] wrote:
> <snip>
>
> I have read the papers, and have AC. I have a lot of printed material
> too. I generally read anything I can find. I stay away from public-
> key because it's a little more then me right now. I understand them,
> just can't do any better.
>
> About TwoDeck, the security lies within not being able to find the
> output of A in B(A(x)), if you don't know A you can't find B.
>
> At anyrate for any N outputs there are N! solutions, and you can't find
> the right one until you have log2(N!) blocks (about 1600 blocks when
> N=256). There is a considerable amount of work required to find the
> one solution that will work.
>
> Am I missing something? Everyone one says it's easy, but I don't see
> how. I really want to know.
>
> Given y = B(A(x)), how do you deduce A or B from it?
>
> Tom
>
> --
> PGP public keys. SPARE key is for daily work, WORK key is for
> published work. The spare is at
> 'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
> 'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
>
> --== Sent via Deja.com http://www.deja.com/ ==--
> ---Share what you know. Learn what you don't.---
------------------------------
From: Tim Maurer <[EMAIL PROTECTED]>
Subject: Re: Review of "Cryptonomicon"
Date: Fri, 14 May 1999 11:56:58 -0500
Greetings,
For those of you who have read "Cryptonomicon," you surely did a whois
on eruditorum.org. Not surprisingly it was registered rather recently,
and there is a bit of a cryptocraphic puzzle at
http://www.eruditorum.org/
Interestin'
-Tim
------------------------------
From: [EMAIL PROTECTED] (Uwe WILHELM)
Subject: WELCOM'99 Submission extended to May 29
Crossposted-To:
comp.org.usenix,comp.security.misc,comp.security.firewalls,comp.lang.java.security
Date: 14 May 1999 19:03:53 +0100
======================================================================
We apologize if you receive this announcement more than once.
======================================================================
Dear Colleagues,
due to several requests we have extended the deadline for submissions to
the "International Workshop on Electronic Commerce 99 (WELCOM'99)" to
*** May 29, 1999 ***
For more information please refer to
http://lsewww.epfl.ch/Events/srds99/welcom/
Yours sincerely,
Uwe Wilhelm
------------------------------
From: [EMAIL PROTECTED] (Christopher)
Subject: Re: Thought question: why do public ciphers use only simple ops like
shift and XOR?
Date: Fri, 14 May 1999 13:25:11 -0400
I find the idea of using a pool of ciphers (with certain requirements)
very interesting. First, if the best option is to use a widely known (and
used) cipher than it seems many reasonably good ciphers simply won't be
used. Whereas the system that uses several ciphers can be thought of as
one widely known system. Presumably this could mean less wasted effort
spent developing ciphers that are on par with existing ciphers, but not
superior enough to justify replacing one already in use.
Also, it is just one more option, which isn't usually a bad thing.
Certain circumstances make implementing such a system fairly
straightforward. In a large organization where one person (or a small
team) is fully trusted with installing and maintaining the security of an
entire network, a fully trusted carrier exists to set up the secret keys
and pools of ciphers. That person just brings the keys to each site
whenever already on site, along with new ciphers for the pool, a list of
obsoleted ciphers, etc.
Having ciphers that becone obsolete every so often has a benefit I haven't
seen discussed here - a cipher no longer used shouldn't garner as much
attention. This property seems to make it more likely that a given
message will never be revealed.
Finally, suppose :
Phase 1 - A 128 bit block cipher, with 128 bit key, that mixes operations
of different math groups on 32 bit sub-blocks
[the key schedule, number of rounds, and (32 bit)functions differentiate
the ciphers in this 'family']
Phase 2 - An 80 bit block cipher, 64 bit key, that works with 5-16 bit
sub-blocks (A,B,C,D,E) such as - A=^B, B=^C, C=^D, D=^E, E=^fn(D, Ks)
[the key schedule, number of rounds, and (16 bit)function differentiate
the ciphers in this 'family']
Phase 3 - A 64 bit block cipher using a Feistal Network and a 64 bit key
[the key schedule, number of rounds, and (32 bit)function differentiate
the ciphers in this 'family']
A 256 bit key ensures each phase uses independent key material.
Each Phase has its own pool of valid ciphers, but reduces the risk of one
cipher (intentionally or not) weakening the final result of the cascade.
And if a minimum amount of diffusion is guaranteed in each phase (to
qualify the variant), the first ciphertext block depends on (all of the
key and) 128 bits of the plaintext, while the rest of the ciphertext
blocks depend on 256 bits of plaintext.
For added strength, the last chunk of plaintext that fits nicely into a
block (in each phase) can be XORed with the first ciphertext block of that
phase, then encipher the last chunk of plaintext (including the last byte)
to ensure that _every_ block of final output is dependant on at least 256
bits of plaintext. This also keeps the ciphertext length equal to
plaintext length, perhaps not desired in some circumstances, but it does
do away with any padding that someone may attack.
Phase 1 by itself (IDEA, for example) seems _very_ secure. But for those
worried that 'someone' has the resources to build large tables of
intermediate results to break that particular cipher, the cascade system
does offer some benefits. The variety of phase 1 ciphers would require
multiple tables (probably not a problem for that 'someone' anyway). But
the additional stages take away the ability of such an opponent to compare
their results to the ciphertext immediately. And it seems intuitively
easier to design functions, at least for phases 2 and 3, that satisfy some
minimum diffusion and key-bit usage requirements - than one cure-all
function that works 'perfectly'.
This is obviously just an example of how I think such a system could
work. But such an example shows how there need not be an implicit risk of
malicious code when adding new ciphers. Each one is merely a description
that could be parsed if need be, and there is a savings on the investment
of the initial implementation in such a design - there's only really two
calls in each phase that change from one variation to the next, the rest
of the code can stay in place.
I shouldn't have to, but I'll point out that these are just my thoughts on
the matter after following the thread for a few days. It has nothing to
do with sides, and, like I said at the beginning of this rather long post,
an idea I found interesting.
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
|:| Multiple encryption, and your method of using many different ciphers
|:| at once, are ways of building in a safety factor, too.
[...]
|:| Since we need a "conventional" design to get the ball rolling even in
|:| this kind of system (i.e., for initial key exchange, agreement on the
|:| choice of ciphers, communicating which ciphers are currently to be
|:| used) if it is _hopeless_ to rely on the security of a single-cipher
|:| system, even if that single cipher is too slow and complicated for
|:| regular use, it seems that the "why bother" argument comes back in
|:| force. Ultimately, even with your multiple cipher scheme used in pure
|:| form - say, for a fixed link, where the choice of ciphers etc. is all
|:| arranged in advance by courier - we still have to cross our fingers
|:| and assume *some* degree of strength for the ciphers being used; but
|:| that does not mean that your scheme can't succeed in making that
|:| assumption - even if still not _provable_ - a lot more plausible.
[...]
|:| John Savard ( teneerf<- )
|:| http://members.xoom.com/quadibloc/index.html
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
