Cryptography-Digest Digest #842, Volume #11 Tue, 23 May 00 09:13:00 EDT
Contents:
Re: OT: Linux international kernel compilation (Mark Wooding)
Re: Crypto patentability (Runu Knips)
Re: Compare 3DES's. (Stefan Lucks)
Asynchronous and simple algorithm ("Martin Winter")
Re: Yet another block cipher: Storin (Mark Wooding)
Re: Yet another block cipher: Storin (David Blackman)
Re: pentium timings ("Brian Gladman")
Re: pentium timings ("Brian Gladman")
Re: Yet another block cipher: Storin (Mark Wooding)
Re: Yet another block cipher: Storin (David Blackman)
Re: Reasonably secure OTP passing ([EMAIL PROTECTED])
Re: Base Encryption: Revolutionary Cypher (Tim Tyler)
Re: Blowfish and Weak Keys ([EMAIL PROTECTED])
Re: Is OTP unbreakable?/Station-Station ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OT: Linux international kernel compilation
Date: 23 May 2000 10:08:35 GMT
Runu Knips <[EMAIL PROTECTED]> wrote:
> Torsten Mohr wrote:
> > i'd like to compile the cryptographic file system for Linux.
> > There are several options in the Makefile to choose, they are
> > mostly related to rpc_gen. Sadly i didn't find any that work
> > for me.
> >
> > Does anybody know a way to compile it? I use the german
> > distribution SuSE 6.4, Kernel 2.2.14.
>
> You're completely offtopic, because this is a NG about crypto
> and not about kernel compilation.
Matt Blaze's Cryptographic Filesystem is actually a user-space NFS
daemon. There's no kernel component necessary.
I have a version of CFS which I've hacked to (a) compile, (b) work
without crashing and (c) provide Blowfish as an additional cipher. If
you send me some mail to [EMAIL PROTECTED], I'll try to remember to send you
a copy.
-- [mdw]
------------------------------
Date: Tue, 23 May 2000 12:14:56 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Crypto patentability
Mok-Kong Shen wrote:
> The Hitachi-AES issue has clearly indicated that there
> are things occuring in the environment that essentially
> concern us but that we barely know of.
>
> I suppose that our group, as the largest (as far as I
> am aware) public crypto community, should form certain
> unified standpoint as to what is and what is not
> patentable in crypto in our conviction, so as to
> (hopefully) influence the future patent policy in the
> same way as in fields of e.g. human gene sequencing.
>
> As a start, I would personally suggest that all single
> operations in the common computer instruction set are
> not patentable, since these have been used in all sorts
> of computations since the very first generation of
> automatic scientific computing. Specific sequences of
> operations are only patentable, if they are clearly
> defined and narrowly delimited with respect to their
> intended purposes and such that they are novel and can
> be demonstrated to lead to significant cryptographical
> advantages (confusion, diffusion etc.). Further, in
> general, The meaning of the sentences in patents should
> be accompanied by mathematical formulations such that
> their proper sense can be easily and unambigiously
> understood by the scientific community.
Fully agreed.
But first, I would simply stop the practice of paying
those people at the patent office for the number of
patents which they accept. Thats like paying a
programmer for the number of lines of code !
------------------------------
From: Stefan Lucks <[EMAIL PROTECTED]>
Subject: Re: Compare 3DES's.
Date: Tue, 23 May 2000 12:24:42 +0200
On Mon, 22 May 2000, Scott Fluhrer wrote:
> Stefan Lucks <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]
> m.de...
[...]
> > -- 2-key triple DES: also about 2^57 encryptions (!) with many chosen
> > plaintexts
> Stefan: do you have details on this attack? Is it similar to your 3-key
> triple DES attack?
I'll try to sketch the attack, which is age-old and due to Merkle and
Hellman.
Recall that 3-key triple DES uses two 56-bit keys. Let us call them L and
M. Given a 64-bit plaintext P, the ciphertext C is produced like this:
A := E_L(P),
B := D_M(A), and
C := E_L(B).
Here, A and B are 64-bit intermediate values.
Now the attacker chooses one fixed value A and produces a table with 2^56
values (P_L,L), where
P_L := D_L(A)
for all DES keys L. Now, there is one plaintext P_L, which under the
correct (but unknown) subkey L encrypts to the first intermediate value A.
The attacker continues as follows: She chooses the plaintexts P_L, asks
for the corresponding ciphertexts C_L, and finally decrypts the P_L under
the key L, i.e. computes
B_L := D_L(C_L).
Now, the adversary still has to find a key M with
D_M(A) = B_L
for some B_L, i.e. with P_M = B_L. Now, any key-pair (L,M) with
P_M = B_L
is a possible solution, and we expect to find about 2^48 such pairs. It
is straightforward to find the correct pair with a negligible number of
extra encryptions.
Thus, this attack needs 2^56 chosen plaintexts P_L (or slightly less
because some collide), and about 2^57 DES encryptions (or rather DES
*de*cryptions).
BTW, yes, my attack on 3-key triple DES has been inspired by this attack.
I tried to make the same principle work for the 3-key variant.
--
Stefan Lucks Th. Informatik, Univ. Mannheim, 68131 Mannheim, Germany
e-mail: [EMAIL PROTECTED]
home: http://th.informatik.uni-mannheim.de/people/lucks/
====== I love the smell of Cryptanalysis in the morning! ======
------------------------------
From: "Martin Winter" <[EMAIL PROTECTED]>
Subject: Asynchronous and simple algorithm
Date: Tue, 23 May 2000 12:44:04 +0200
Hi all,
I have to implement some security into an online game that has to store the
score, e-mail address... of the user to a webserver. Since the language I
have to program in is very limited (Lingo in Macromedia Director/Shockwave),
I am desperately looking for a more or less simple asynchronous encryption
algorithm because the prices for the best players are quite nice (cellular
phones, computers etc.)
I already hid the score and other important variables during the game in
memory, but my algorithm for sending the data to the server is simply very
bad. Since I am in no way an expert in cryptology and - as I said - the
language I am programming with on the client side is very limited (I even do
not have the ability for bit-shifting!), I really need some hints.
On the server side I can create a Perl script to decrypt the data from the
client.
Hope to get some help from you experts, or just some links to good
documentation. (Too bad that the links on
http://theory.lcs.mit.edu/~rivest/crypto-security.html are somewhat
outdated)
Martin
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Yet another block cipher: Storin
Date: 23 May 2000 10:54:32 GMT
Manuel Pancorbo <[EMAIL PROTECTED]> wrote:
>
> Mark Wooding <[EMAIL PROTECTED]> escribió en el mensaje de noticias
> I'm designing an algorithm based on matrix multiplication and from my
> experience the higher the field is, the worse the diffusion is, mainly in
> the higher bits of the plaintext. As I see you use GF(2^24) which is very
> high. So, the effort on diffusion must be made by other part of your
> algorithm.
No, I don't use GF(2^{24}): I use Z_{2^{24}}, which isn't a field but
contains lots of invertible elements. This is a good thing: a matrix
multiplication over GF(2^n) would be linear with XOR! As the MARS paper
comments, integer multiplication provides excellent nonlinearity in the
high-order bits.
The matrix multiplication seems to be very good at diffusing changes
upwards, towards the most significant ends of the words. The linear
transformation is intended to be (a) simple, and (b) provide downwards
diffusion. It seems to be quite good at it. I get full avalanche after
three rounds, and I'm fairly close after two.
The matrix has been chosen to provide good diffusion *between* words.
Eaxctly one element in each row and column is even. This is the best
you can get out of a 4x4 matrix, I think -- putting four odd numbers in
the same row or column loses you invertibility.
Earlier versions used a rotation instead of the current (slightly
bizarre) x XOR (x >> 12) construction. I changed because, firstly, my
target architectures aren't very good at rotation -- you have to
synthesize them from shifts, which ends up being almost as expensive as
the matrix (!) -- secondly, it has better diffusion properties anyway,
and, finally, since it's an involution, it clearly provides exactly the
same diffusion in the reverse direction, shutting the doors on chosen
ciphertext attacks.
-- [mdw]
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: Yet another block cipher: Storin
Date: Tue, 23 May 2000 21:14:21 +1000
Manuel Pancorbo wrote:
>
> Mark Wooding <[EMAIL PROTECTED]> escribió en el mensaje de noticias
> [EMAIL PROTECTED]
> > The main operation is multiplication by a fixed invertible 4x4 matrix over
> > Z_{2^{24}}.
>
> I'm designing an algorithm based on matrix multiplication and from my
> experience the higher the field is, the worse the diffusion is, mainly in
> the higher bits of the plaintext. As I see you use GF(2^24) which is very
> high. So, the effort on diffusion must be made by other part of your
> algorithm.
It gets excellent diffusion between the different words, and also from
low order to high order bits within words. It does nothing from high
order to low order bits.
Mark tries to fix that by adding the linear step: x = x ^ (x >> 12) to
get some information back to the low bits. It should work.
I wonder if a better linear step might be x = x - (x>>24) , assuming the
the dot product was calculated to at least 48 bits. This should still be
fast on a DSP. With a bit of thought it can be invertible (evil grin:-).
It would be a pain to code in ANSI C though.
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Tue, 23 May 2000 12:20:09 +0100
"Jerry Coffin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] says...
>
> > It is unequivocally incorrect to call RDTSC and expect it
> > to return anything resembling what you may expect unless you
> > serialize the processor first. The easiest way to do this is to
> > execute the CPUID instruction before every instance of RDTSC.
Jerry is correct here - RDTSC without CPUID serialisation provides a poor
basis for the timing of low cycle count routines (such as many encryption
algorithms). I soon discovered this when I set up code to do AES algorithm
timing.
I did not find a large effect in using more than one CPUID instruction for
initialisation but without any CPUID serialisation I found that I could be
out by as much as 30 cycles in 300. As Jerry says, another problem is code
alignment since this can make a big difference to timing. For really
accurate results code needs to be run at a number of different alignments to
see whether this has an impact. This can make a very big difference to
results. Cache effects are also large so it is important to decide what
result is being timed (timings with or without cache filling).
Removing the effect of interrupts is relatively easy since timing a number
of times and taking minimum timings (or by removing timings beyond 3
standard deviations from the mean and recalculating) eliminates the odd
(rare) interrupt event that occurs. Other effects can be removed by timing
the code by using one call to it for 'initialisation' and then timing it for
one execution and for two executions and taking the difference - this is
what I ended up with for AES timing after doing hundreds of experiments and
looking for reasonable repeatability. But I still would not trust my
timings to better than +/-5% in absolute terms.
Brian Gladman
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Tue, 23 May 2000 12:20:39 +0100
"Jerry Coffin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] says...
>
> > It is unequivocally incorrect to call RDTSC and expect it
> > to return anything resembling what you may expect unless you
> > serialize the processor first. The easiest way to do this is to
> > execute the CPUID instruction before every instance of RDTSC.
Jerry is correct here - RDTSC without CPUID serialisation provides a poor
basis for the timing of low cycle count routines (such as many encryption
algorithms). I soon discovered this when I set up code to do AES algorithm
timing.
I did not find a large effect in using more than one CPUID instruction for
initialisation but without any CPUID serialisation I found that I could be
out by as much as 30 cycles in 300. As Jerry says, another problem is code
alignment since this can make a big difference to timing. For really
accurate results code needs to be run at a number of different alignments to
see whether this has an impact. This can make a very big difference to
results. Cache effects are also large so it is important to decide what
result is being timed (timings with or without cache filling).
Removing the effect of interrupts is relatively easy since timing a number
of times and taking minimum timings (or by removing timings beyond 3
standard deviations from the mean and recalculating) eliminates the odd
(rare) interrupt event that occurs. Other effects can be removed by timing
the code by using one call to it for 'initialisation' and then timing it for
one execution and for two executions and taking the difference - this is
what I ended up with for AES timing after doing hundreds of experiments and
looking for reasonable repeatability. But I still would not trust my
timings to better than +/-5% in absolute terms.
Brian Gladman
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Yet another block cipher: Storin
Date: 23 May 2000 11:32:00 GMT
David Blackman <[EMAIL PROTECTED]> wrote:
> I wonder if a better linear step might be x = x - (x>>24) , assuming the
> the dot product was calculated to at least 48 bits.
Hmm. Interesting.
I wanted to avoid doing addition or subtraction in the `linear' step, to
dissuade attacks which consider integer addition and multiplication to
be linear: the only `nonlinear' step would then be the key mixing. I
believe that the expression for L(x) is sufficiently horrible to be an
adequate deterrent. ;-)
> This should still be fast on a DSP. With a bit of thought it can be
> invertible (evil grin:-).
You're right that getting the full 48-bit result would be just as quick.
I'm not entirely sure how you make it bijective. You'd need to get the
high 24 bits of the results back from somewhere, but the matrix
arithmetic stops being over a convenient pseudofield and everything
falls apart. Or am I wrong?
A possibility that was considered and rejected was to just take the top
bits of the result and use a Feistel network to restore bijectivity.
I'm fairly cautious about nonbijective Feistel networks because I'm not
keen on giving attackers free 2-round iterative characteristics.
> It would be a pain to code in ANSI C though.
This would be unfortunate. Doing the various bits of analysis was
painful enough as it was.
-- [mdw]
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: Yet another block cipher: Storin
Date: Tue, 23 May 2000 22:03:15 +1000
Mark Wooding wrote:
>
> David Blackman <[EMAIL PROTECTED]> wrote:
>
> > I wonder if a better linear step might be x = x - (x>>24) , assuming the
> > the dot product was calculated to at least 48 bits.
> > This should still be fast on a DSP. With a bit of thought it can be
> > invertible (evil grin:-).
>
> You're right that getting the full 48-bit result would be just as quick.
> I'm not entirely sure how you make it bijective. You'd need to get the
> high 24 bits of the results back from somewhere, but the matrix
> arithmetic stops being over a convenient pseudofield and everything
> falls apart. Or am I wrong?
Hint: make sure the constant matrix elements are relatively prime to 2
** 24 + 1, and small enough that the dot product never excedes 48 bits.
Correct and efficient handling of the 2 ** 24 case will be amusing, but
just barely possible i think.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Reasonably secure OTP passing
Date: Tue, 23 May 2000 12:11:39 GMT
On another point , OTP is primarily a station to station
protocol...Has there been any discusion or papers on how to use OTP as a
multi-station protocol...i.e. if you want to send an encrypted messages
to different users at different times..how do you synch the OTP key...?
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> On Sat, 20 May 2000 14:11:27 GMT, [EMAIL PROTECTED]
> (John Savard) wrote, in part:
>
> >Send, enciphered very thoroughly, a whole bunch of OTPs, each of
which
> >comes with an identifying number. Now, the cryptanalyst also has to
> >determine which OTP one's message is related to...
>
> >and if a returning message is sent with a header (all also enciphered
> >thoroughly in a conventional system) identifying _two_ of the OTPs,
> >and starting points within them, the cryptanalyst has quite a search
> >task ahead before even starting the difficult job of analyzing the
> >correlations between two enciphered texts.
>
> I found a spot in my web page where it seemed appropriate to put this
> notion, explained more fully and with a diagram,
>
> http://www.ecn.ab.ca/~jsavard/mi060901.htm
>
> which page has been expanded in a couple of other spots as well. I
> also added a picture of the resistor (and mica capacitor, but I didn't
> go into that level of detail) color code and the color code of pool
> balls to the introductory page (to accompany Braille and semaphore)
>
> http://www.ecn.ab.ca/~jsavard/intro.htm
>
> plus, a new image was added to the page on the fourth dimension. I
> haven't updated my page in a while, and the last few things done with
> it were the addition of new additional topics; the encryption part has
> been static.
>
> John Savard (teneerf <-)
> http://www.ecn.ab.ca/~jsavard/
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Base Encryption: Revolutionary Cypher
Reply-To: [EMAIL PROTECTED]
Date: Tue, 23 May 2000 12:13:48 GMT
wtshaw <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
:> wtshaw <[EMAIL PROTECTED]> wrote:
:> : Eric Lee Green <[EMAIL PROTECTED]> wrote:
:> :> ....All bases can be represented in base 2, albeit with some
:> :> wasted bits for odd-number (non-power-of-2) bases. Adding other bases thus
:> :> can be considered to be a very crude block-cipher diffusion
:> :> mechanism, i.e., a mechanism for diffusing bits across a larger
:> :> field of bits, with some properties that make it decidedly
:> :> inferior to most such mechanisms for transforming bits (for one
:> :> thing, a 1-bit change in the input does not have the desired
:> :> avalanche property).
:>
:> : You are quoting dogma which happens to be mathematically wrong. Base 2 is
:> : only fundamental to other powers of two.
:>
:> You are attacking a position which was never presented.
: You furnished the quote that says essentially this.
You appear to me to have interpreted this quote in a manner which was
not intended.
:> Eric never said: "base 2 is only fundamental to other powers of two."
:>
:> He said: "All bases can be represented in base 2", which may be unclear -
:> but is unlikely to be wrong.
: There are values that cannot be expressed clearly as a number in all
: systems; base two is a system, hense it is true that some numbers cannot
: be definitively expressed as values in base two. Consider that pi even
: transcends all normal bases in this regard.
Some real values have longer expansions in some bases than others.
Since we're discussing discrete systems intended for cryptography, I
assume that infinite expansions should not normally be involved.
: Consider that pi can be used as a base having values that can only be
: approximated in other bases.
Non-integer bases? Surely this is not related to the subject at hand?
: Part, an important part, is that there is distingishing differece between
: bases in efficiency. Also, various manipulations are most awkward in base
: two [...]
I would usually say the reverse. Computers operate with logic gates, in
base 2.
If there's an alternative, trying to construct another base on top of this
on efficiency grounds will usually be a bad move - due to a mismatch with
the underlying hardware.
:> If a systems fails to have proper avalanche properties when viewed from
:> the perspective of base 2, it's likely to be completely stuffed.
:
: You can see the properties you like and have poor properties in another
: base. [...]
...but you can't see a failure to get avalanche in *any* base and have
good overall diffusion properties. If your system exhibits good
avalanche properties, it should not be possible to transform it into
another base, and watch the avalanche disappear. If you can do this, the
system has undesirable cheracteristics in that base.
This is the case Eric was describing. He wasn't seeing avalanche, and
erroneously concluding that therefore, the effect would happen in all
bases. He was seeing a /lack/ of avalanche - and concluding that the
system was broken.
: The point not that bit twiddlers are not doing good things, it is
: that unless other evaluations are considered, binary constructors can
: blindsight themselves, never know that this is the case because the fail
: to look.
A binary construction that demonstrates a lack of avalanche will not
become invalid if you consider other bases. If there's a significant
lack of avalanche in base 2, the cypher's bound to be broken.
FWIW, my view of base changes in cryptography, is that they are
essentially a diffusion operation. They have minimal confusion
properties on their own.
I am not inclined towards them for several reasons. For one thing, they
diffuse much better in one direction than in the other - to get
good "reverse" diffusion, you probably need to reverse and change base
again. I also prefer small, "atomic" diffusion operations that can be
interleaved with confusion stages. You generally need to interleave
diffusion with confusion to prevent the diffusion being undone in a single
step. Compared to the small, fast operations I prefer, a base-change
offers better diffusion - but is fatter and slower. Then there's the fact
that any non-2 prime base has no non-wasteful representation in hardware.
My criticisms are mainly aesthetic - but I take the lack of such
operations in most existing systems to indicate that others agree.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Goodbye cool world.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Blowfish and Weak Keys
Date: Tue, 23 May 2000 12:26:38 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mark Wooding) wrote:
>
> That's right. You can detect a weak key by searching each S-box for
two
> identical words. A simple hashtable will work for this. You can just
> use the least significant bits of each entry as its hash.
>
> Note that nobody has discovered a way to detect the use of a `weak'
key
> in full 16-round Blowfish, let alone exploit it. You're probably
> wasting your time.
Actually I've found that Vaudenay's 'weak' key detection technique
can be extended to the full 16-round Blowfish (if I'm not mistaken).
As I see it, the main limiting factor in Vaudenay's approach is the
use of an r-2 round differential which means that only half of the
ciphertext can be examined to see if the differential has held.
This gives a 32-bit filtering condition with the effect that trying
to push the method beyond r=14 rounds results in an insufficient SNR
to be able to isolate 'random' effects from differential effects.
The extension is very simple - use an r round differential.
Although this reduces the probability of the differential holding,
it does give you a 64-bit filtering condition because the whole
of the ciphertext can be checked to see if the differential held.
This much improves the SNR with the result that r=16 rounds becomes
possible.
The downside of all this though, is that about 2^60 chosen plaintexts
are required, which makes it all completely impractical of course!
Add to this the fact that (as you point out) we don't know how to
exploit it anyway, it makes me wonder why they're called 'weak' keys
in the first place!
Anyway, I've got some notes on this at home (deriving the 2^60 CP)
which I can try to put in electronic form if anyone is interested.
Paul(o)
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is OTP unbreakable?/Station-Station
Date: Tue, 23 May 2000 12:27:01 GMT
One of the major limitations of OTP is its a Station to Station
Protocol...if there are more then two users having the random
keypad...sending OTP messages to different users at different times is a
major headache...you have to sync the random keys..i.e. if you have 5
users...all with the same pad...
You send a message to user 1
you also have to send dummy messages to the other users telling them you
have used that key...they inturn will drop that key..and the next key
will become the active key...
That can be very problematic with a large user community...
Since its also been shown that sending the index of the random sub-key
in a long random key could possibly breaks the OTP ....thats also not an
option...
So at most, an OTP can only be used successfully as a Station to Station
protocol...
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
