Cryptography-Digest Digest #678, Volume #12 Thu, 14 Sep 00 08:13:00 EDT
Contents:
Re: sac fullfilling decorelated functions (Serge Vaudenay)
Re: Disappearing Email redux (Guy Macon)
Music Industry wants hacking information for cheap ("David C. Barber")
SDMI Crypto Challenge ("David C. Barber")
Re: SDMI Crypto Challenge (Jim Gillogly)
Re: SDMI Crypto Challenge (Jim Gillogly)
Re: Hash algorithms (Runu Knips)
Re: Problem with Tiger hash algorithm and binary files (Runu Knips)
Re: security of SKID based msg authentication. (Roger Gammans)
Re: sac fullfilling decorelated functions (Tom St Denis)
Re: cellular automata rng? (Tim Tyler)
Re: [Q] Design criteria for sboxes in Tiger/192 ? (Tim Tyler)
Re: Scottu19 Broken (Tim Tyler)
Re: Police want help cracking code to find Enigma machine (Anders Thulin)
----------------------------------------------------------------------------
Date: Thu, 14 Sep 2000 11:29:54 +0200
From: Serge Vaudenay <[EMAIL PROTECTED]>
Subject: Re: sac fullfilling decorelated functions
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> Mike Rosing <[EMAIL PROTECTED]> wrote:
> > Tom St Denis wrote:
> > >
> > > Let's take F(x) = a.x + b in GF(2)^32, now we want to know for any
> > > multiple of 'a' in the same field what is the prob of at laest 16
> bits
> > > being set... so I take out some new finite I learnt and plug in (32
> > > choose 16)/2^32 = 2^-2.837. This means about 1 in 6 will be SAC
> > > fullfilling functions.
> > >
> > > Over the entire multiplcation we find 32/6 ~ 5.3 which means of the
> 32
> > > multiples of 'a' only 5 are sac fullfilling. If 'a' is random there
> > > distribution should be random (?). Now consider the lower bits,
> such
> > > as with only four bits set. We find them with a prob of 2^-16.865
> much
> > > less then with 16 bits.
> > >
> > > In any GF multiply the chances of any being of only four bits is
> about
> > > 2^-11 or 1 in 2048. This means that GF multiplication is a closely-
> sac-
> > > like function most of the time, and for a fraction of the time not.
> > >
> > > Can this be used to extract information from the function in those
> > > specific cases (extreme cases?)
> >
> > F is linear. That's a much bigger problem :-)
>
> Actually in Vaudenays paper if 'a,b' is random the function is immune
> to linear cryptanalysis.
>
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
It is actually a little tricky.
If you consider differential cryptanalysis with any input difference a
and any output difference b, the probability DP(a,b) depends on the
secret key. We can show that *on average over the key*, this probability
is too low to be useful, which shows that a random linear cipher resists
to differential cryptanalysis.
People argue that we can implement extensions of differential
cryptanalysis
(BTW we never claimed that the linear cipher was secure), but if you
look
at any formally proven security result against differential
cryptanalysis,
it is exactly the same. For instance the PURE cipher also has the
property
that for any fixed differential characteristic, the probability over the
key distribution is low.
Result for linear cryptanalysis is similar.
You can think about this technique as a way to strengthen regular
ciphers.
For instance, you can prove that AES o F o CAMELIA has no useful
differential
or linear cryptanalysis. This is the COCONUT construction.
COCONUT is still vulnerable against other attacks like Wagner's
boomerang
attacks. But you can notice that Boomerang attack has a complexity which
is
the square of the complexity of differential attacks. So if we already
need
2^64 pairs to break AES or CAMELIA by using differential attacks, we
will
need 2^128 pairs in order to break AES o F o CAMELIA with boomerang
attack.
I will try to update the decorrelation home page which is now available
on
http://lasecwww.epfl.ch
Serge Vaudenay
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Crossposted-To: alt.privacy,uk.legal
Subject: Re: Disappearing Email redux
Date: 14 Sep 2000 10:08:27 GMT
Tommy the Terrorist wrote:
>To the
>contrary, I see this stuff in the privacy policy (which to be fair is no
>more weaselly-worded than any other privacy policy on the Internet......)
Contrast this with the privacy policy at [ http://www.freedom.net ]...
(Note that Zero-Knowledge is selling a different kind of service
and that I am not commenting on the merits of the service that
Disappearing Inc. is selling.)
"Zero-Knowledge can neither decipher the contents of private e-mail
or private chat room communications nor determine the true identity
of any subscriber transmitting such content over the Freedom Network.
However, Zero-Knowledge has the right, but not the obligation, to
disclose (to the extent it is technically able to do so) encrypted
private communications if, Zero-Knowledge, in its sole discretion,
reasonably believes that such action is necessary to comply with
applicable law or valid legal process. Freedom uses cryptographic
algorithms which renders Freedom Nym� communications virtually
impossible for any agency or individual (including Zero-Knowledge)
to decrypt without the applicable keys."
In other words, they will disclose ciphertext in order to avoid
legal action against them. That's all they can give, by design.
"A concerted court ordered attack on multiple Freedom Server
Operators, however, could result in a nym's pseudonymity being
compromised. If multiple server operators were forced to reveal
their encryption keys, it would be possible to determine a
particular nym's e-mail address or IP address. In addition,
a sufficiently powerful organization could, if so desired,
retrieve the informational content of mail sent to regular
Internet users by monitoring Internet network access points
around the world. Each of these attacks would require significant
resources in order to pursue and force the revelation of keys
controlled by third-party Freedom Server Operators."
Fair warning about the weaknesses of their system...
"Note that Zero-Knowledge does not own or control any Freedom
Server Operators. We can only use our best efforts to obtain
their cooperation in any of these situations. For more details
regarding the strength of Freedom's privacy implementation,
see the Freedom Papers."
BTW, if you are concerned about someone controlling every
Freedom Server Operator (which would crack this or any other
system!), you can become a Freedom Server Operator yourself.
The software is free and the users choose which Freedom Servers
to relay through.
"Zero-Knowledge falls under the laws of the government of Canada,
and may be obliged to respond to warrants and subpoenas coming
from courts under Canadian jurisdiction. Complaints from other
governments will be dealt with on a case by case basis."
Again, they don't promise not to give up what they have. Your
protection comes from the fact that nobody but you and your
reciever have your cleartext, nobody but the first Freedom Server
in the chain knows who you are, and nobody but the last Freedom
Server in the chain ou choose knows who your recipient is.
------------------------------
From: "David C. Barber" <[EMAIL PROTECTED]>
Subject: Music Industry wants hacking information for cheap
Date: Wed, 13 Sep 2000 14:16:34 -0700
Our wonderful music industry is looking for hacking information, but sure
doesn't want to pay much for it. www.hacksdmi.org is offering $10K for
anyone who can defeat SDMI II before its release. Hardly what such
information would be worth unless it's just a couple days work for some
clever person.
Wonder what it will cost them if (when?) SDMI II is cracked *after* its
official release?
(SDMI for the not completely informed is Secure Digital Music Initiative.
The concept is that they can embed information into the music stream that
cannot be filtered out, will survive various
decompression/recompression/format conversions, and will still tell SDMI
compliant players not to play or allow copies. This is all while the rest
of the world chugs along on MP3.)
*D B*
------------------------------
From: "David C. Barber" <[EMAIL PROTECTED]>
Subject: SDMI Crypto Challenge
Date: Wed, 13 Sep 2000 14:23:24 -0700
The music industry is paying (underpaying) $10K for anyone who can defeat
the SDMI-II proposals. Visit www.hacksdmi.com for info.
*David Barber*
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: SDMI Crypto Challenge
Date: Thu, 14 Sep 2000 10:39:59 +0000
"David C. Barber" wrote:
>
> The music industry is paying (underpaying) $10K for anyone who can defeat
> the SDMI-II proposals. Visit www.hacksdmi.com for info.
There are no details at http://www.hacksdmi.com yet, so I don't know
whether they're planning to make the algorithms and/or source code
available, or whether it's another of these bogus CYA "Here's some
content, can you read it?" challenges. In any case, they're allowing
only three weeks, so I'm guessing they aren't hoping for real information.
--
Jim Gillogly
Highday, 23 Halimath S.R. 2000, 10:38
12.19.7.9.17, 6 Caban 20 Mol, Eighth Lord of Night
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: SDMI Crypto Challenge
Date: Thu, 14 Sep 2000 10:52:21 +0000
Jim Gillogly wrote:
>
> "David C. Barber" wrote:
> >
> > The music industry is paying (underpaying) $10K for anyone who can defeat
> > the SDMI-II proposals. Visit www.hacksdmi.com for info.
>
> There are no details at http:// www.hacksdmi.com yet, so I don't know
> whether they're planning to make the algorithms and/or source code
> available, or whether it's another of these bogus CYA "Here's some
> content, can you read it?" challenges. In any case, they're allowing
> only three weeks, so I'm guessing they aren't hoping for real information.
Sorry, that should be http://www.hacksdmi.org .
--
Jim Gillogly
Highday, 23 Halimath S.R. 2000, 10:51
12.19.7.9.17, 6 Caban 20 Mol, Eighth Lord of Night
------------------------------
Date: Thu, 14 Sep 2000 13:00:14 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Hash algorithms
[EMAIL PROTECTED] wrote:
> I have a project that requires me to look into 5 hash algorithms
A hash algorithm is an algorithm which gives you a checksum of
some data. There are hash functions for different purposes,
noticeably for the realization of hash tables.
In Crytography, the hash functions should be cryptographically
hard, i.e.
(a) the function should create a result which is long enough to
make brute force attacks impossible
(b) it should not be possible to get from the hashsum any
information about the document.
(c) it should not be possible to create a document which creates
a given checksum.
(d) it should not be possible to find two documents which have
the same checksum.
Cryptographically hard hash functions are used, for example,
to prove that someone has some kind of information. If I have
a document and want to know if you have it too, I ask you for
the hashsum. If you can give it to me, it has been prooved
that you have that document.
Hash functions are really a new concept in cryptography.
Interesting hash functions are MD2, SHA-1, RIPE MD160 and Tiger.
Of historical interest are MD4 and its successor MD5, also
Snefru and Snefru-8.
------------------------------
Date: Thu, 14 Sep 2000 13:11:03 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Problem with Tiger hash algorithm and binary files
Daniel Leonard wrote:
>
> On Wed, 13 Sep 2000, Konrad Podloucky wrote:
>
> > From Eli Biham's Tiger page
> > (http://www.cs.technion.ac.il/~biham/Reports/Tiger/):
> > "[...]Note that in the original reference implementation that we have
> > published in this page there was a typo that used the wrong bit
> > order when it padded the '1' bit at the end of the message. It
> > used the constant 0x80, rather than 0x01 to append this bit. The
> > reference implementation and test results given above are already
> > corrected. We are grateful to John Lull who found this typo."
>
> This confused me more because while discussing with Mr. Antoon Bosselaers,
> he told me that the correction was wrong.
Well, in fact it is a question of intepretation. If you have, say, 12
bits of information
111111111111
and need to get the hash sum of it, you have to store the first 8 bits
in a first byte, then you have to decide: (a) you put bit 9 of your
information into (a) the lsb OR (b) the msb of the second byte. In
the first case, the 2 bytes have the values ( 0xff, 0x0f ), in the
second case their values are ( 0xff, 0xf0 ).
This means that both intepretations are possible. Saying that one
is more 'correct' than the other leads to a "fight" like "little
endian" against "big endian", not in gulliver, but in computer
technology. x86 and alpha are little endian, sparc and ppc are
big endian, and even worse is mips which might be little or big
endian, depending upon the setup.
If, for Tiger, the lsb is the first bit, its simply okay.
------------------------------
From: [EMAIL PROTECTED] (Roger Gammans)
Subject: Re: security of SKID based msg authentication.
Date: Thu, 14 Sep 2000 11:32:14 GMT
In article <8ppdk1$d8t$[EMAIL PROTECTED]>, Scott Fluhrer wrote:
>Roger Gammans <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> 2) Bob choses a random number (Rb) , He then sends Alice:-
>> Rb,M,H(K,Ra,Rb,M,B)
>>
>> 3) Alice can then also compute H(K,Ra,Rb,M,B) to
>> verify the message came from Bob.
>>
>> So are there any _really_ glaring errors in this? - Beyond of
>> course the security of H().
>Obvious problems:
>
>- Mallet can request any message he wants from Bob. He pretends to be
>Alice, picks a random number (aka nonce) Ra, and sends it to Bob with a
>request for message M. Bob sends back the response which includes M in the
>cleartext. Now, Mallet can't verify that Bob really sent it, but he may be
>willing to take his chances.
Ah. Ok.
Not actually a problem I to worried about for the area I intend
to use this for.
Because the request actually goes over a seperate channel to the response.
The request channel may or may not be secure, but theres nothing
I can do about this, and quite frankly if it isn't secure
it is a case of `all bets are off'.
But I do want to be sure the response is tied relavitely sanely to the
request, and this is all I really need to manage.
>- When Alice asks Bob for message M, Mallet can intercept that message, and
>replace it for a request for message N with the same nonce Ra. Bob then
>sends back Rb,N,H(K,Ra,Rb,N,B), and Alice then procedes with the assumption
>that message N is the message she asked for.
Again an attack against the request. Good.
More serious admittedly, but it still requires Mallet to get access
to the request channel.
If I make the recieve side available (as OS) though I must remember to
comment along these lines though.
Thanks, TTFN
--
Rogere
Think of the mess on the carpet. Sensible people do all their
demon-summoning in the garage, which you can just hose down afterwards.
-- [EMAIL PROTECTED]
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: sac fullfilling decorelated functions
Date: Thu, 14 Sep 2000 11:43:38 GMT
In article <[EMAIL PROTECTED]>,
Serge Vaudenay <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > Mike Rosing <[EMAIL PROTECTED]> wrote:
> > > Tom St Denis wrote:
> > > >
> > > > Let's take F(x) = a.x + b in GF(2)^32, now we want to know for
any
> > > > multiple of 'a' in the same field what is the prob of at laest
16
> > bits
> > > > being set... so I take out some new finite I learnt and plug in
(32
> > > > choose 16)/2^32 = 2^-2.837. This means about 1 in 6 will be SAC
> > > > fullfilling functions.
> > > >
> > > > Over the entire multiplcation we find 32/6 ~ 5.3 which means of
the
> > 32
> > > > multiples of 'a' only 5 are sac fullfilling. If 'a' is random
there
> > > > distribution should be random (?). Now consider the lower bits,
> > such
> > > > as with only four bits set. We find them with a prob of 2^-
16.865
> > much
> > > > less then with 16 bits.
> > > >
> > > > In any GF multiply the chances of any being of only four bits is
> > about
> > > > 2^-11 or 1 in 2048. This means that GF multiplication is a
closely-
> > sac-
> > > > like function most of the time, and for a fraction of the time
not.
> > > >
> > > > Can this be used to extract information from the function in
those
> > > > specific cases (extreme cases?)
> > >
> > > F is linear. That's a much bigger problem :-)
> >
> > Actually in Vaudenays paper if 'a,b' is random the function is
immune
> > to linear cryptanalysis.
> >
> > Tom
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
>
> It is actually a little tricky.
> If you consider differential cryptanalysis with any input difference a
> and any output difference b, the probability DP(a,b) depends on the
> secret key. We can show that *on average over the key*, this
probability
> is too low to be useful, which shows that a random linear cipher
resists
> to differential cryptanalysis.
Which is just a different way to resist differential cryptanalysis
right?
> People argue that we can implement extensions of differential
> cryptanalysis
> (BTW we never claimed that the linear cipher was secure), but if you
> look
> at any formally proven security result against differential
> cryptanalysis,
> it is exactly the same. For instance the PURE cipher also has the
> property
> that for any fixed differential characteristic, the probability over
the
> key distribution is low.
>
> Result for linear cryptanalysis is similar.
>
> You can think about this technique as a way to strengthen regular
> ciphers.
> For instance, you can prove that AES o F o CAMELIA has no useful
> differential
> or linear cryptanalysis. This is the COCONUT construction.
>
> COCONUT is still vulnerable against other attacks like Wagner's
> boomerang
> attacks. But you can notice that Boomerang attack has a complexity
which
> is
> the square of the complexity of differential attacks. So if we already
> need
> 2^64 pairs to break AES or CAMELIA by using differential attacks, we
> will
> need 2^128 pairs in order to break AES o F o CAMELIA with boomerang
> attack.
If you have seen my earlier posts such as TC6a you will see I used the
decorrelated function as my round function. Would you suggest that as
a insecure design?
> I will try to update the decorrelation home page which is now
available
> on
> http://lasecwww.epfl.ch
Book marked :)
Thanks for the clarification.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: cellular automata rng?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 14 Sep 2000 11:31:36 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: I was reading up Wolfman's paper on CA and the cryptanaylsis as well []
: Here's my question. Let's say I have a 2048 bit (multiple of 32 :) )
: CA state, can I take the first n bits to encode n-bit blocks per
: clocking? Or do I have to spread the sampling of n-bits througout the
: state (every 2048/n bits) or can I only take one bit at a time?
Wolfram generally considered taking one-bit-at-a-time.
Obviously, taking all the bits would obviously be "very bad".
If you're sampling n bits on every cycle, you *can't* take bits 0-n.
Bits 1 - n-1 in the naxt time step depend only on known information
from the previous time step :-(
Sparse sampling would no-doubt be somewhat better than "very bad".
Wolfram didn't have any boundary conditions, IIRC.
Any practical implementation would have to impose periodic boundary
conditions (null boundary conditions don't work well with rule-30).
FWIW, I prefer the Hortensius autotmata [1]. These are a lot like LFSRs,
in that they're linear, and can be constructed with guaranteed minimum
periods - something you won't get from rule-30 automata. Rule-30
automata with periodic boundary conditions aren't even reversible -
each reachable state has two possible precursors, IIRC - and there are
many states that are inaccessible.
Of course, the Hortensius automata have no strength - but rule-30 isn't
exactly strong either.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
[1] Hortensius, P. D., McLeod, R. D., Pries, W., Miller, D. M. and Card,
H. C., Cellular automata-based pseudorandom number generators for
built-in self test, IEEE Transactions on Computer-Aided Design, August
1989, volume 8, number 8, pages 842-859.
Hortensius, P. D., McLeod, R. D.and Card, H. C., Parallel random
number generation for VLSI systems using cellular automata, IEEE
Transactions on Computers, 1989 volume 38, number 10, pages 1466-1473.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: [Q] Design criteria for sboxes in Tiger/192 ?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 14 Sep 2000 11:35:40 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
[secret s-boxes]
: I don't know. But I like to point out that the same
: question apparently could apply to almost all well-
: known block ciphers that have S-boxes, starting with
: DES, whose design rationales are kept secret even
: today. [...]
These were published by IBM, IIRC. Aren't they as stated on A.C. p. 294?
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Scottu19 Broken
Reply-To: [EMAIL PROTECTED]
Date: Thu, 14 Sep 2000 11:40:41 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: Suppose an English-language novel contained text like:
: da boiz bEEt, him puRt-
: y gud?!
: Unless the author was in total control and deliberately
: introduced the equivalent of C obfuscation for plot purposes,
: any sane person would not suggest that the author would have
: done better to write the novel in verse form, or with
: marginal notes, etc. The real problem would be incompetence
: in the use of basic linguistic tools.
Anthony Burgess (A Clockwork Orange) may probably be excused on the
grounds you mention. I wonder if James Joyce (Finnegan's Wake) could
make use of a similar excuse... ;-)
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Anders Thulin <[EMAIL PROTECTED]>
Subject: Re: Police want help cracking code to find Enigma machine
Date: Thu, 14 Sep 2000 11:51:28 GMT
Mike Rosing wrote:
> An actual method of contact which is both secure and safe for both
> sides. The blacked out paragraph may state something publicly,
> and have the real method hidden.
From whom should the real message be hidden? If it was sent to
a newspaper, and so intended to be widely published ... perhaps,
as the real recipient would be Bletchley Park, but they would
get it over an open channel. (Requires some explanation as to why
this roundabout way was chosen.)
But since it apparently was sent to the musuem, it doesn't seem
to fit very well: unless there's a message to an insider in it
... even so, it seems odd to be in a situation to require
steganographic techniqes for communication. (Perhaps the sender
could not afford more than one stamp? :)
Well, we don't know the whole message: there probably is something
important in the removed part and the signature.
(Thinking a bit ...)
I can't think of a likely scenario incorporating both the theft,
the time up to now, and the published text of letter as well as the use of
steganography. Those I *can* think of, all include interpreting the
date of the theft as a message as well.
A semi-literate writer seems more likely to me.
It will be interesting to see what happens next.
--
Anders Thulin [EMAIL PROTECTED] 040-10 50 63
Telia Prosoft AB, Box 85, S-201 20 Malm�, Sweden
------------------------------
** 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
******************************
