Cryptography-Digest Digest #679, Volume #11 Mon, 1 May 00 16:13:01 EDT
Contents:
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
("donoli")
Re: Interleaving for block encryption (Mok-Kong Shen)
New Twofish Tech Report (Bruce Schneier)
Re: Joystick as RNG (wtshaw)
Re: sboxes for the bored... (Tim Tyler)
Re: Autocorrelations (Mok-Kong Shen)
Re: mod function? ("Douglas A. Gwyn")
Re: Should there be an AES for stream ciphers? (Tim Tyler)
Re: mod function? (Mok-Kong Shen)
Re: Karatsuba threshold ("Michael Scott")
Re: about search and seisure of computers again (JimD)
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net" (JimD)
Re: Joystick as RNG (Mok-Kong Shen)
Re: Why is this algorithm insecure? (Newbie flamefodder) ([EMAIL PROTECTED])
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net" (Dan
Day)
----------------------------------------------------------------------------
From: "donoli" <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk
Subject: Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the
net"
Date: Mon, 01 May 2000 18:21:53 GMT
Dave J wrote in message ...
>On Sun, 30 Apr 2000 03:26:17 -0700, Hawke <[EMAIL PROTECTED]>
>wrote:
>
>>very interesting reading.
>>I can see where this is starting to become a trend.
>>What is with the governments of this planet these days?
>>they cannot even trust their own citizens?????
>>
>>sorry for the massive cross-post reply.
>>
>>Hawke
>>
>>
>>NoSpam wrote:
>>
>>
>>http://www.sunday-times.co.uk/news/pages/sti/2000/04/30/stinwenws01034
>>.html
>
>Would someone who knows the score (legal and otherwise) tell me about
>unseen problems with headerless encryption?
>I believe the data part of a pgp file is indistinguishable from white
>noise so if the software was altered a little to encrypt the header as
>well the authorities couldn't tell the difference between your code and an
>analogue recording of white noise..?
>In my simple minded view I think that makes the legislation unworkable.
>Ok, so they can do you for not providing a key even if you don't have it
>but can they do you for a bunch of random numbers that isn't even
>demonstrably encrypted?
>
>I am currently learning C, partly with an eye to borrowing the PGP source
>code and altering the header generation. I am *sure* there must be snags I
>haven't thought of but as I'm usually taken as the local nutter I can't
>get a sensible reply..
>
>Anyone?
>
>Dave J.
##############
How are you going to alter the header if you're not using a remailer when
the header is generated by the sever and not your PC?
donoli.
##############
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Interleaving for block encryption
Date: Mon, 01 May 2000 20:48:01 +0200
Paul Koning wrote:
> Mok-Kong Shen wrote:
> >
> > In channel encoding there is a technique for dealing
> > with burst bit errors named interleaving (or code
> > splicing). Analogously applied to block encryption
> > with a cipher of block size, say, 64 bits, this would
> > mean first to accumulate 64 blocks of plaintext and
> > then to take all first bits of the given blocks to
> > form one block as input to the cipher, then take all
> > second bits of the given blocks, and so on. This seems
> > to be beneficial to strength, since in bruteforcing the
> > opponent would need to tackle at least 64 blocks.
>
> I must be missing something.
>
> The blocksize is still 64 bits; you still need only
> one cipherblock to do a (known plaintext) brute force
> attack. Yes, those 64 bits come from 64 plaintext
> blocks, one bit apiece, but so what?
>
> Besides, you need to assume attacks where thousands
> or millions of blocks of plaintext and ciphertext
> are available, so increasing a requirement from
> 1 to 64 is not particularly interesting...
Probably one fairly useful situation is what I mentioned after what you
quoted in my original post, namely in conjunction with variable keys,
i.e. with different keys for different blocks, in case one doesn't yet
feel
satisfied with the variable key approach.As to factor, the same factor
may have different significances, depending on what gets multiplied.
Compare e.g. the case of day with that of month or year.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: New Twofish Tech Report
Date: Mon, 01 May 2000 18:41:09 GMT
Key Separation in Twofish
J. Kelsey
Twofish Technical Report #7, April 7, 2000
ABSTRACT: In [Mur00], Murphy raises questions about key separation in
Twofish. We discuss this property of the Twofish key schedule, and
compare it with other block ciphers. While every block cipher has this
property in some abstract sense, the specific structure of Twofish
makes it an interesting property to consider. We explain why we don't
believe this property leads to any interesting attacks on Twofish, and
describe what such attacks will have to look like if they do exist.
http://www.counterpane.com/twofish-tr7.html
**********************************************************************
Bruce Schneier, Counterpane Internet Security, Inc. Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Joystick as RNG
Date: Mon, 01 May 2000 11:54:10 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> It seems to me that use of a joystick is /very/ much like use of a mouse -
> though more people have a mouse - and they are more likely to be wiggling
> it while operating programs requiring seeds to be generated.
Create a physical maze on your screen, negotiate it with your mouse.
Harvest you location on the screen mod x at some y interval. This is one
of may ways to get random numbers, but unless a part of your encryption
program, you will have to store the sequence. Best yet, do some sort of
game and hide the encryption program as an option in the code; build the
random sequence to some useful level, then use it. It'll drive 'em nuts
having to look for such crypto if secreted in gaming software....cheers.
--
Laughter is often the most pleasing result of successful analysis.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: sboxes for the bored...
Reply-To: [EMAIL PROTECTED]
Date: Mon, 1 May 2000 18:47:23 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
: in sci.crypt Tim Tyler <[EMAIL PROTECTED]> wrote:
:>Terry Ritter <[EMAIL PROTECTED]> wrote:
[...]
: I really don't like 4-bit substitution tables because they are just
: so weak.
I hope your distaste would be tempered by the existence of real block
cyphers whose non-linear component is wholly 4x4 s-boxes. It appears that
both GOST and Serpent rely entirely on 32x32 arrays of 4x4 s-boxes for
their confusion element. Serpent also includes an initial and final
permutation - but the designers say that this should not be considered to
have any cryptographic significance.
>From this it appears to me that 4x4 s-boxes can result in reasonable
strength - if enough of them are used.
: That said, I have (effectively) used such tables (e.g.,
: in Latin square construction), which required testing the result
: to see if it differed from the ideal.
Testing would not be acceptable when building large combiners.
If you wind up with results which differ in a detectable way from the
ideal distribution, then you probably need to employ more small boxes,
or a different way of combining them.
:>: But diffusion is *the* issue: we can't just handwave that into
:>: existence. Producing an even diffusion from boxes which always cover
:>: 4 contiguous bits is going to be a problem, and I have serious doubts
:>: that it can be resolved.
:>
:>I've done some experimentation with 4x4 boxes in exploring
:>non-uniform "Margolus neighbourhood" cellular automata [this was based on
:>a system like the Java applet automaton at http://hex.org.uk/diffusion/ ].
:>As a result of this, uniform diffusion from 4x4 boxes seems quite
:>attaniable in practice.
: I was not aware of the reference, thanks.
: But I don't think it delivers the type of information one needs to
: understand diffusion in a block cipher. [snip empirical diffusion test]
: We might even use data and key in patterns to try and expose any
: statistical weakness we can find.
: *That* is what we mean by diffusion throughout the block.
Essentially I'd agree that this is what would be required in order to
produce an experimental verification of good diffusion properties.
I don't pretend to have done anything remotely approaching this volume of
work. What I /have/ done suggests to *me* that getting good diffusion
will prove attainable. I'm not in a good position to demonstrate this to
anyone else at the moment.
It appears that GOST and Serpent get good diffusion by alternating their
non-liner confusion s-boxes with simple linear diffusion - rather than by
relying solely on the s-boxes themselves.
:>: Another approach is to have each 2nd-level box take a bit from a
:>: different top level box [...]
:>
:>Yes. The main reason I don't look terribly closely at such designs is
:>that the violate locality, and thus do not make for such high speed
:>operation in hardware.
: I am not unfamiliar with hardware design, and while routing arbitrary
: interconnections on a two-dimensional surface is always a problem,
: here we have a very structured routing. I would think we need
: traverse only the width of a modest bus if we route the bus along the
: table array. I don't see a whole lot of slowdown there.
The problem is one of dimensions. If you have only two tables to link
together then this presents no problem. The problems arise when we have
many tables, which need to be stacked up.
Some diagrams:
Imagine we have 16 bits: |A1 A2 A3 A4|B1 B2 B3 B4|C1 C2 C3 C4|D1 D2 D3 D4|
S-boxes are applied that permute all the As, all the Bs, etc.
Then all the 1s, all the 2s and all the 3s.
If this only needed to be done once then the array:
|A1 A2 A3 A4|
|B1 B2 B3 B4|
|C1 C2 C3 C4|
|D1 D2 D3 D4|
...could be used. All the As are adjacent, as are all the 1s, etc.
However, the only way to stack a number of these constructions would
be to use the third dimension. If we are confined to two-dimensional
silicon, the best solution looks like this:
|A1 A2 A3 A4|B1 B2 B3 B4|C1 C2 C3 C4|D1 D2 D3 D4|
| | | | | | | | | | | | | | | | (permute by letter)
|A1 A2 A3 A4|B1 B2 B3 B4|C1 C2 C3 C4|D1 D2 D3 D4|
| | | | (permute by number)
| +--------+ | | (other connections not shown)
| | +-----------------+ |
| | | +--------------------------+
|A1 A2 A3 A4|B1 B2 B3 B4|C1 C2 C3 C4|D1 D2 D3 D4| (repeat...)
| | | | | | | | | | | | | | | | (permute by letter)
|A1 A2 A3 A4|B1 B2 B3 B4|C1 C2 C3 C4|D1 D2 D3 D4|
| | | | (permute by number)
| +--------+ | | (other connections not shown)
| | +-----------------+ |
| | | +--------------------------+
|A1 A2 A3 A4|B1 B2 B3 B4|C1 C2 C3 C4|D1 D2 D3 D4| ... and so on.
This involves too many long wires for my taste. The wires cross over
one another. The wider you make the block size, the more wires are
needed, and the more the speed of update for each individual round
reduces.
Yes, you can get more diffusion in each round if you do this sort of
thing - but it does seem to have its costs if you need to squeeze the
result into a two-dimensional silicon space.
:>[...]
:>: But if we *only* use 4-bit tables with maximum nonlinearity, we have
:>: changed the universe of nonlinearity distribution: we have performed a
:>: selection which may be identifiable and useful to the opponent.
:>
:>This seems a general point of philosophical debate in s-box construction -
:>to select them or to simply make them large. Selecting them can
:>help defend against the attacks of the day - while /possibly/ weakening
:>them against the attacks of tomorrow. I'm in favour of selection.
: I don't think this debate is just philosophical: I doubt this is a
: "designer's choice," at least at the 4-bit level. By selecting only
: those tables with good nonlinearity it seems quite likely that some
: consequent statistics are going become useful in differentiating one
: table from another.
Individual tables can easily be distinguished from random ones - but I
doubt large enough composites of them can be.
If you don't like the selection, an alternative would be to use *random*
4x4 tables. This is what was done in some variants of GOST.
It's my impression that using the linear tables is a waste of time. If
you use them, you need to add more rounds to compensate for the linear
tables - which don't really do much of use. IMO, they can be usefully
omitted.
:>While we have performed a selection, we've selected in such a manner
:>to /avoid/ the states which may be useful to the opponent (the linear
:>tables).
: But linearity is only part of the problem: We have to defend against
: *any* attack, not just symbolic manipulation. Any statistic which can
: distinguish between different tables would be very worrisome.
Yes, but the resulting composite table made of the many small
s-boxes should not be more non-linear than normal. It should
look like a random permutation, just like any block cypher.
:>: For example, if the set of all acceptable boxes is not bit-balanced, then
:>: the opponent can expect to find a bias and possibly even localize it.
:>
:>I'd expect each acceptable box to be a 4-bit permutation - which is
:>balanced in every useful way. Consequently the set of them will also
:>be balanced.
: Well, there is balance and balance. *Obviously* each permutation is
: balanced. But the subset of nonlinearity 4 boxes may well have
: distinguishing characteristics beyond the obvious. Clearly, they are
: distinguished by nonlinearity value; why would we suspect that nothing
: else distinguishes?
The composite tables should /not/ be distinguishable from real ones by
non-linearity - and it is the properties of such arrays of smaller boxes
that we are interested in. Anomolies of the individual components are
irrelevant unless they wind up affecting the properties of the final
result.
:>: In contrast, we can get better diffusion from just two 256-byte 8-bit
:>: orthogonal Latin squares and just one 16-bit memory access (we store
:>: both squares together as 16-bit elements).
:>
:>My construction as it stood required 24 x 8 bytes = 192 bytes of LUT.
:>Your construction uses 2 x 256 = 512 bytes of LUT. It's not very
:>suprising yours is likely to have better properties.
: Exactly my point: If we *can* measure a difference in properties from
: the ideal, we have inherently shown the design to be insufficient. We
: can't just say, "Oh, well, it doesn't really work, but it was cheap."
Cheap designs that don't work are useless - unless they indicate how to
construct more expensive designs that /do/ operate correctly.
I gave my example to indicate one way of combining small s-boxes into
larger ones - in the face of criticism that combining 4x4 boxes in
series would only ever result in another 4x4 box.
I said at the time that I had not included enough layers. I did not
include them because I wanted to make my diagram smaller.
[snip]
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ This tagline no verb.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Autocorrelations
Date: Mon, 01 May 2000 21:01:38 +0200
Marty wrote:
> A simple way to think about it is to note that any correlating process
> that produces a different distribution than a random sequence produces
> information about that sequence.
Sorry for my poor comprehension capability. I can't yet get from
what you wrote an idea of how to (qualitatively or quantitatively) assess
the autocorrelations of X_t and Y_t from the properties of its components.
Would you please elaborate a little bit?
BTW, could you give a literature pointer to the 'perfect' (void of) auto-
correlation of primitive Galois polynomials that you mentioned in the last
post? I like to learn the proof. Thanks.
M. K. Shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: mod function?
Date: Mon, 1 May 2000 18:09:28 GMT
Dave Ashley wrote:
> Any function where the derivative changes sign can be viewed as an
> equivalence relation of some sort.
That wasn't what Bob was doing.
However, I think he was overreacting; "a mod n" makes sense
in Z, and "a mod n = b mod n" (evaluated in Z) is the usual
way of implementing his preferred notation "a = b mod n".
Embedding Z/n in Z is pretty benign.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Should there be an AES for stream ciphers?
Reply-To: [EMAIL PROTECTED]
Date: Mon, 1 May 2000 19:00:46 GMT
Gregory G Rose <[EMAIL PROTECTED]> wrote:
: Look up "NESSIE" [...]
NESSIE: New European Schemes for Signatures, Integrity, and Encryption
https://www.cosic.esat.kuleuven.ac.be/nessie/
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: mod function?
Date: Mon, 01 May 2000 21:20:28 +0200
Richard Parker wrote:
> Not to worry, the pages in question demonstrate 'mod' as an equivalence
> relation and distinguishes it from 'mod n' modular reduction and the modulo
> operator that appears in some programming languages. I just didn't want to
> cause the original poster additional confusion by modifying his language.
I don't yet quite understand the debate. If one does any computation,
whether in theoretical derivation or practical computing, mod does not
seem to differ in any aspect from abs or other real-valued functions.
On the other hand, in programming one has to note that in some
programming languages the specification doesn't prescribbe whether for
x mod y with x negative and y positive the compiler should return a
positive result.
M. K. Shen
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: Karatsuba threshold
Date: Mon, 1 May 2000 20:26:29 +0100
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Michael Scott wrote:
> > For (an extreme) example GF(2) "multiplication" (carry-free
multiplication -
> > in GF(2) add and subtract are both XOR) is not supported by any
instruction
> > set I know of. Therefore it must be implemented by a shift-and-xor
program.
>
> ? GF(2) multiplication is simply the AND operator. Almost all
> instruction sets have an operator that will AND all bits in a
> word in parallel.
Yes, sorry, sloppy notation. I meant multiplication over GF(2^32) if the
word length is 32 bits. As described in P1363 Appendix A3.4
Mike Scott
------------------------------
From: [EMAIL PROTECTED] (JimD)
Crossposted-To: alt.privacy.anon-server,alt.privacy
Subject: Re: about search and seisure of computers again
Reply-To: JimD
Date: Mon, 01 May 2000 18:39:43 GMT
On Sun, 30 Apr 2000 19:26:51 -0400, jungle <[EMAIL PROTECTED]> wrote:
>wipe by 3 passes under PGP ...
>
>NO ONE recovered data, NO ONE provided prove,
>that data wiped with above description has been recovered, except providing
>over exaggerated statement that "it's maybe possible to recover" ...
>
>correct me when I'm wrong, by facts not by myths only ...
>
>I have f/d [ 1.44 mb ] wiped by pgp 3x information to recover, no one like to
>be famous for attempting recovery, but many "experts" are arguing that data
>recovery is possible after wiping it 7x times by pgp, which is more than 2
>times wiped that I have ...
Possible, but unlikely, and in any case enormously expensive
just to make the attempt in the hope of recovering useful
data.
--
Jim Dunnett.
g4rga at thersgb.net
Londoner? Vote for Ken!!
------------------------------
From: [EMAIL PROTECTED] (JimD)
Subject: Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
Reply-To: JimD
Date: Mon, 01 May 2000 18:39:44 GMT
On Mon, 1 May 2000 11:05 +0100 (BST), [EMAIL PROTECTED] (Nick Barron) wrote:
>In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] (NoSpam) wrote:
>
>> MI5 is building a new £25m e-mail surveillance centre that will have the
>> power to monitor all e-mails and internet messages sent and received in
>
>Hmmm, £25m to monitor *everything*? My, they do get their kit cheap, don't
>they :)
Absolutely! That's before they even start thinking about the
staff, the massive storage systems, the dictionary computers....
--
Jim Dunnett.
g4rga at thersgb.net
Londoner? Vote for Ken!!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Joystick as RNG
Date: Mon, 01 May 2000 21:46:52 +0200
wtshaw wrote:
> Create a physical maze on your screen, negotiate it with your mouse.
> Harvest you location on the screen mod x at some y interval. This is one
> of may ways to get random numbers, but unless a part of your encryption
> program, you will have to store the sequence. Best yet, do some sort of
> game and hide the encryption program as an option in the code; build the
> random sequence to some useful level, then use it. It'll drive 'em nuts
> having to look for such crypto if secreted in gaming software....cheers.
I think that it continues to be regreted that, while there
are many good means to collect randomness from physical
devices, the problem of convenient transport of the sequences
obtained to the communication partners for use in crypto
applications yet waits to be satisfactorily solved. That's
why I am personally still biased towards PRNGs.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Why is this algorithm insecure? (Newbie flamefodder)
Date: Mon, 01 May 2000 19:37:38 GMT
> Sorry, I may have disremembered. I thought I'd read somewhere (trade
> press) that a bunch of machines had worked for about a month on - RSA,
> was it? I forget. It was within the last six weeks or so, but of
course
> I could have it all wrong. Please bear in mind that I'm not a
> cryptographer, so I (illogically) tend to be less critical of articles
> on cryptography in the trade rags than I do about C articles.
>
You may be thinking of the effort by distributed.net. Appx 100,000 PCs
and a $250,000 custom DES cracking machine from the EFF broke the DES
III challenge in 22 hours, 15 minutes.
Distributed.net held the previous record at cracking DES with a 56 hour
time to deciphering. Both times the algorithms were 56-bit.
In the end, the EFF "Deep Crack" machine found the key, which was a bit
disappointing in that some piddly P5-90 didn't find it, but it still
was rather interesting that a non-profit organization with relatively
little budget built such a good DES machine.
RSA Press release:
http://www.rsasecurity.com/news/pr/990119-1.html
DES III challenge home page:
http://www.rsasecurity.com/rsalabs/des3/
Graphs of Rate in G Keys/sec vs time:
http://www.distributed.net/statistics/des3/index.html
Distributed.net has been working on deciphering an RC5-64 project for
about 921 days as of 5-1-00. They're 23% of the way done, working at an
overall rate of 54,000,000 KKeys/sec. At the current rate of
116,085,969 KKeys/sec (of 5-1-00) they have 1,410 days left.
Not a small task by any measure.
Regards,
Nathan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk
Subject: Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
Date: Mon, 01 May 2000 20:06:12 GMT
On Sun, 30 Apr 2000 10:24:47 +0100, "NoSpam" <[EMAIL PROTECTED]> wrote:
>
>The government already has powers to tap phone lines linking computers, but
>the growth of the internet has made it impossible to read all material. By
>requiring service providers to install cables that will download material to
>MI5, the government will have the technical capability to read everything
>that passes over the internet.
This crap is getting out of hand.
------------------------------
** 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
******************************
