Cryptography-Digest Digest #917, Volume #10 Mon, 17 Jan 00 05:13:01 EST
Contents:
Re: "1:1 adaptive huffman compression" doesn't work (Peter Rabbit)
Re: SRP optimisation (Keith Burdis)
Re: Cracking DES (Paul Schlyter)
Re: Cracking DES (Paul Schlyter)
Re: Cracking DES ("Douglas A. Gwyn")
Re: Ciphers for Parallel Computers (Mok-Kong Shen)
Re: Cracking DES ("Douglas A. Gwyn")
Re: New Crypto Regulations (Arturo)
----------------------------------------------------------------------------
From: Peter Rabbit <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: "1:1 adaptive huffman compression" doesn't work
Date: Mon, 17 Jan 2000 08:40:12 GMT
Peter Rabbit wrote:
>
> Tim Tyler wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > : Tim Tyler wrote:
> > :> :> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > :> :> : Tell me in what sense the software is not portable?
> > :> :>
> > :> :> If you have no convenient source of genuine randomness, it won't work.
> > :> :> Not every system comes with a good hardware source of random numbers.
> > :> :> If you use something []at all [p]redictable, you introduce possible
> > :> :> problems.
> > :>
> > :> : I don't understand what 'possible problems' you would have.
> > :>
> > :> The attacker knows something about the data in the compressed file,
> > :> information which he need not be supplied with. He knows it is likely
> > :> to have certain non-random stuff at its end. This is less than ideal.
> >
> > : Are you going to argue like those who unconditionally want 'absolute'
> > : security?
> >
> > Clearly there's no such thing.
> >
> > : Note that one never gets 100.00% pure gold in this world,
> > : there is always some foreign atoms in there. Returning to the present
> > : case, we are discussing about the (practical) problem raised by Scott.
> > : Do you think that my proposed scheme has 'practically' solved the
> > : problem or not?
> >
> > In practice, the Huffman ending problem appears to offer the attacker few
> > footholds anyway. Seven bits per message may compromise some systems,
> > but not very many. At worst it knocks this number of bits off the
> > keyspace. Most systems should withstand this, most of the time.
> >
> > I don't know if your scheme reduces the problem to acceptable levels.
> > What is "acceptable" depends on your application.
> >
> > I see your scheme as an source of unnecessary and easily eliminated
> > potential weakness. I don't see what the problem is with using the ideal
> > Huffman file ending scheme, now that it has been discovered.
> >
> > : How does one proceed to exploit the 'certain non-random stuff'?
> >
> > I've given in some detail one way the analyst might get information from
> > this, even if the padding is /totally/ random.
> >
> > Giving the analyst unnecessary information about plaintext statistics in
> > messages is not a good idea. I'm sure you can figure out what an analyst
> > can do with such information for yourself.
> >
> > : Please tell me a 'concrete' way to get some 'information' out of
> > : these that is 'actually' sensible to his task, namely to decrypt
> > : to obtain the information in the bit sequences 'preceeding'
> > : these 2 filling bits.
> >
> > If he has one message, his job is not easy. Also, your question
> > is not necessarily the right one. With two bits of information, he's
> > not going to get /much/ useful information about the rest of the message -
> > unless the message has a two bit key.
> >
> > I've explained how /even/ totally random padding can give the analyst
> > information he wouln't haveif a deterministic compressor had been used,
> > that might help identify the sender.
> >
> > I'm uncertain why I face yet more questions along the same lines.
> >
> > Haven't I made my point already?
> >
> > :> : In fact, I don't need 'true randomness', nor even
> > :> : 'pseudo-randomness', only 'non-constancy'.
> > :>
> > :> This won't do at all, IMO.
> >
> > : Please explain.
> >
> > You think (say) preferentially padding with zeros is generally acceptable
> > behaviour, despite the fact that it gives away probably-known plaintext?
> >
> > Would you more more concerned if you were padding to a 128-bit block
> > rather than an 8-bit one?
> >
> > : Don't just put up a claim without any supporting material [...]
> >
> > I was under the impression that giving away probable plaintext to
> > attackers was generally considered undesirable. I'm a bit puzzled
> > about being asked for "supporting material". The attacker gains
> > statistical knowledge about the plaintext, which was previously
> > unavailable to him. What more do I need to say?
> >
> > You want me to spell out how to analyse frequency information in
> > messages, when statistical characteristics of the plaintext are
> > known?
> >
> > I'll give an example, which should demonstrate how an analyst might be
> > helped.
> >
> > He has a bunch of messages, which he knows from the context of
> > their interception contain encyphered-compressed password data.
> >
> > The passwords were generated by a random number generator.
> >
> > Each password is encyphered with its own key.
> >
> > The analyst wants access to the passwords.
> >
> > [In this instance compression doesn't help, but the compressor was built
> > into the cypher-machine.]
> >
> > The analyst has access to a captured table of keys to the cypher
> > - but he doesn't know where the user started in his key table, so he tries
> > starting positions one at a time, assuming consecutive keys were used
> > for consecutive messages, as specified in the manual of a captured
> > machine.
> >
> > Since the messages themselves are random, his only source of information
> > is the padding used by the compressor. If he decyphers a large number of
> > password files in a row, and they exhibit the same statistical anomalies
> > that are introduced by the padding scheme of the compressor, he knows he
> > has found the correct starting key.
> >
> > None of this would have bneen possible, were it not for a very few
> > non-random bits information appended to the files.
> >
> > :> : In particular, periodicity will do perfectly well for my proposal.
> > :> : Let's take the case where the plaintext (true one, or the wrong
> > :> : one because of wrong decrypting key) is such that there need to
> > :> : be 2 filling bits. Suppose the software is such that on the first
> > :> : use it emits 00, the second time 01, the third time 10, the fourth time
> > :> : 11, the fifth time 00, etc. Now suppose what the analysyt has after
> > :> : decrpytion is a version with filling bits 00. He decompresses it
> > :> : to the (presumed) plaintext and compresses that back again. There
> > :> : are four different possibilties of the result. But in NO case can
> > :> : he obtain any information, because he knows that any difference
> > :> : is due to the 'ideosyncracies' of the compression software and
> > :> : is not related at all to the 'proper' information in the file.
> > :>
> > :> That doesn't appear to be correct. Imagine the case where he has a
> > :> complete known-plaintext attack on the cypher that recovers the key,
> > :> and several consecutive known plaintexts. He can thus determine what
> > :> padding bits have been used by the compressor. If he is intercepting
> > :> all messages, he thus has information about what the padding bits are
> > :> most likely to be on the next message, should that message require two
> > :> padding bits. This is information he would not normally have, which may
> > :> assist him with any attack.
> > :>
> > :> Of course, if he only has one message to work on, then - as you say -
> > :> he's no better off.
> >
> > : In the example case mentioned above, all four filling bit patterns are
> > : 'equally likely', there is no 'most likely' one. Could the analyst
> > : still do something with his 'statistical data' of the filling bits?
> >
> > You said they were used in sequence. Consequently he knows that if the
> > message has a two-bit padding - he knows which two bits will be used.
> >
> > Consequently some bits *are* more likely than other ones - despite each
> > two-bit sequence being used with equal frequency.
> >
> > Can the attacker do anything with this? It's not very likely that he can
> > do much with 1/4 of a bit. Analysts are clever folk, though. I wouldn't
> > like to say it was always totally useless.
> > --
> > __________
> > |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
> >
> > Mobius strippers never show you their back side.
>
> I've been following this argument for a while now and find the whole
> thing to be moot! The only time a generic Zipper becomes a problem is if
> the encryption program that takes the zipped file and encrypts it
> without changing the position of the BYTES. Take the following
> example...
>
> (read in 16k at a time...)
>
> DIM MixBox(0 to 16383) as Integer
>
> for x=0 to 16383
> MixBox(x)=x
> Next
>
> k=Int(Rnd*1000) 'or something
>
> for x=0 to 16383
> k=(k+MixBox((x+13257))mod 16383 'or something like it
> 'now swap things around
> c=MixBox(x)
> MixBox(x)=MixBox(k)
> MixBox(k)=c
> Next
>
>
> In the encryption routine you add...
>
> cipher(x)=Plain(MixBox(x)) etc. etc
>
> Now you have BYTE 15383 (or something) in position #1 of your
> Ciphertext and BYTE 283 (o.s.) in position #2. After encryption I'd like
> to see where the bad Zipper left its fingerprints so that a smart
> attacker can use them to attack the file. Only a poor encryption algo
> implementation would leave the data where it found it. That is an
> invitation for a plaintext (ziptext) attack!
>
> Peter Rabbit
------------------------------
From: Keith Burdis <[EMAIL PROTECTED]>
Subject: Re: SRP optimisation
Date: 17 Jan 2000 08:53:36 GMT
John Myre <[EMAIL PROTECTED]> wrote:
> Keith Burdis wrote:
> <snip...>
>> M1 = H(B,M1,K)
>> M2 = H(A,B,K)
> The definition of M1 makes no sense. Do you mean M1=H(B,M2,K)?
Yes, sorry. That's what I meant.
>> Does having the server send its evidence first adversely affect the
>> security of SRP in any way?
> Now the adversary can do an off-line password guessing attack. With
> the four-message version, the server doesn't provide M2 (which can be
> used to verify a guess of a password) until it checks M1 (which proves
> knowledge of the password). In theory, with SRP you can't check a
> password guess except by trying to log on, as long as you don't break
> in to the server itself.
> (The attack on the 3-message version would be: start the log on, then
> quit as soon as you get M2. Then guess different passwords until you
> can compute M2 yourself).
You are quite correct. I've included a full description of the details of
the attack below. (This description was also posted to the SRP mailing
list).
> John M.
I thought that I had discovered a simple optimisation for Optimised
SRP that would further reduce the number of message exchanges
necessary for mutual authentication, but as explained by John Myre on
the sci.crypt newsgroup, this "optimisation" made an offline
dictionary attack possible. I think it may be useful to describe what
I tried and why it didn't work.
The normal optimised SRP as described in Tom Wu's ISOC paper is as
follows:
Client Server
-- C,A --->
<--- s,B --
-- M1 --->
<-- M2 --
where:
* M1 = H(A,B,K)
* M2 = H(A,M1,K)
After the first message from the client, the server has sufficient
information to derive the session key and produce the evidence
necessary to prove that it knows the session key. With my
"optimisation", the acceptor presents evidence that it knows the
shared session key along with the data it sends in its first message,
rather than doing so after the initiator presents its evidence in
round three:
Client Server
-- C,A --->
<--- s,B,M2 --
-- M1 --->
where:
* M2 = H(A,B,K)
* M1 = H(B,M2,K)
This means that mutual authentication takes the same number of message
rounds as unilateral authentication does.
However, as explained by John Myre, this makes it possible for an
attacker pretending to be a legitimate client to undertake an offline
dictionary attack:
"Now the adversary can do an off-line password guessing attack.
With the four-message version, the server doesn't provide M2
(which can be used to verify a guess of a password) until it
checks M1 (which proves knowledge of the password). In theory,
with SRP you can't check a password guess except by trying to
log on, as long as you don't break in to the server itself.
(The attack on the 3-message version would be: start the log on,
then quit as soon as you get M2. Then guess different passwords
until you can compute M2 yourself)."
- John Myre, sci.crypt newsgroup, 14 January 2000
This attack is described in more detail as follows:
1. The attacker discovers the client's username (C). This is easy
since the username is transmitted in the clear.
2. The attacker generates its ephemeral asymmetric keypair (a and A)
as normal and sends C and A to the server.
3. The server sends s, B and M2 to the attacker.
4. The attacker aborts the connection.
At this point the attacker has knowledge of the following data:
n, g, a, A, B, s, H(A,B,K)
The following formulae are used by a client to compute the session
key (K):
x = H(s,P)
S = (B-g^x)^(a+ux)
K = H(S)
(It is assumed that u is computed as a simple function of B.)
The attacker has sufficient information to compute a candidate K using
a guessed password (P). It is then able to verify whether or not this
candidate K is correct or not using the evidence given by the server:
H(A,B,K)
since it has knowledge of both A and B.
It is therefore important that the client prove its knowledge of the
session key before the server does so, because in order to do so the
client needs to have knowledge of the real password.
Thanks very much to John Myre for pointing out the problem.
- Keith
--
Keith Burdis - MSc (Computer Science) - Rhodes University, South Africa
IRC: Panthras JAPH QEFH
---
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Cracking DES
Date: 17 Jan 2000 08:43:00 +0100
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> Paul Schlyter wrote:
>> OK, but then you must have some other way to determine whether
>> you've obtained the correct cleartext or not.
>
> That's pretty easy, unless the PT has no characteristics that
> distinguish it from a uniformly random set of bits.
>
> ZFUDAFYLAVBQPOCBKPAGUSRRGNCPQEGFN
> vs.
> NOWISTHETIMEFORALLGOODMENTOCOMETO
>
> There are several simple statistical tests that can distinguish
> between such putative PTs, and for a large sample they are
> highly reliable.
And what if the cleartext isn't ASCII, but some binary information?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Cracking DES
Date: 17 Jan 2000 08:43:23 +0100
In article <[EMAIL PROTECTED]>,
JPeschel <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (Paul Schlyter) writes:
>
>>In article <[EMAIL PROTECTED]>,
>>JPeschel <[EMAIL PROTECTED]> wrote:
>>
>>> [EMAIL PROTECTED] (Paul Schlyter) writes:
>>>
>>>> The only known way to crack single DES is by brute force: if you have
>>>> one cleartext-cryptotext pair, try all possible keys until you
>>>> encounter the correct key.
>>>
>>> It's not always necessary for an attacker to possess one cleartext-
>>> cryptotext pair.
>>
>>OK, but then you must have some other way to determine whether
>>you've obtained the correct cleartext or not.
>
> Of course.
Any suggestions how to do that?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cracking DES
Date: Mon, 17 Jan 2000 09:32:22 GMT
Paul Schlyter wrote:
> In article <[EMAIL PROTECTED]>,
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > Paul Schlyter wrote:
> >> OK, but then you must have some other way to determine whether
> >> you've obtained the correct cleartext or not.
> > That's pretty easy, unless the PT has no characteristics that
> > distinguish it from a uniformly random set of bits.
> > ...
> > There are several simple statistical tests that can distinguish
> > between such putative PTs, and for a large sample they are
> > highly reliable.
> And what if the cleartext isn't ASCII, but some binary information?
In the above, I removed the example that you let confuse you.
Try reading it now. It has nothing to do with ASCII.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Ciphers for Parallel Computers
Date: Mon, 17 Jan 2000 10:51:26 +0100
Douglas A. Gwyn wrote:
>
> Mok-Kong Shen wrote:
> > If one can arrange that brute-force is the only practically viable
> > approach of attack, ...
>
> Almost never the case.
If I don't err, EFF's cracking of DES is brute-force. Of course,
you could consdier the ingenuity of building hardware there and
say it wasn't brute-force. But I think one should take some more
or less subjective common criteria in that. Is factoring with the
Fermat method brute-force? I suppose most people would answer 'yes'.
How about quadratic sieve? I personally consider that also to be
brute-force, but you might disagree. I believe it is probably
correct to say that the classical ciphers were mostly not solved
via brute-force, while many modern ciphers are by design so
sophisticated that brute-force is practically the cheapest way of
attack.
> > In an admittedly very imprecise sense I suppose that the analyst is
> > generally forced to brute-force if the algorithm design is such that
> > the whole scheme cannot be formulated in terms of a small set of
> > mathematical equations of fairly simple nature with the key as
> > the variable.
>
> Also almost never the case. However, just because one has a set of
> equations doesn't mean that they are easy to solve. For example,
> known PT and CT might yield (upon plugging in all those constants):
>
> K0(1+K2)K3 + (1+K0)K1K2K3 + K1K2(1+K3) = 0
> K0K2 + (1+K0)(1+K1)K3 + K1K2K3 = 0
> (1+K1)(1+K3) + K0K1(1+K3) + K0K3 = 0
> K0(1+K1)(1+K3) + K1(1+K2)(1+K3) + K0K1K2K3 = 0
>
> which is a set of 4 simple equations in GF(2)^4, but so far as I
> know there is no general methodology for solving such systems that
> takes appreciably less work than a brute-force search over the domain
> (for larger systems, anyway). If it were a set of *linear* equations
> it would be easy to solve, but no cryptographer who knows his business
> would design a system whose encryption equations were linear in the
> key variables.
Let's again consider DES. One has a small set of fairly clean-looking
equations. However, the working of the S-boxes isn't a straightforward
substitution of 4 bits, the mapping of the 4 bits is sort of 'context
sensitive' via the outer 2 of the 6 input bits, i.e. the plaintext
plays a 'controlling' role. Further, from a global standpoint,
the left part of the plaintext is used to encrypt the right part
and vice versa. Thus the key is (in certain sense) not the 'only'
governing variable in the set of equations. One could formulate
such that the key is the only governing variable, but then the set
of equations would be fairly weird, I am afraid. I believe that
these facts render DES difficult (inefficient) to attack with
methods other than brute-force. As said, I guess that one general
way of forcing (or more or less forcing) brute-force would
be a design such that a description via a certain not too large
set of equations in terms of the key (alone) as 'variable' is
not possible in practice (because it would be extremely clumsy, or
barely comprehensible with a 'surveying eye', etc. etc.) There could
be other conceivable ways of forcing brute-force, of course. It would
thus be very nice, if readers of this thread would like to contribute
their ideas/opinions on this issue.
M. K. Shen
==========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cracking DES
Date: Mon, 17 Jan 2000 09:59:36 GMT
Paul Schlyter wrote:
> Any suggestions how to do that?
Sure, but you really ought to exert a *little* effort and read
some of the tutorial material suggested in the sci.crypt FAQ.
The simplest test is the so-called delta I.C., which is equivalent
to the 0th component of the autocorrelation of the CT and several
other ways of computing a simple "distribution" statistic, e.g.
Pearson's chi-square against the hypothesis of uniform random.
E.g. given the putative PT 11010101111001110011101111011101, the
null hypothesis is that the sample came from a parent population
with equal probability for 0 vs. 1; tally up the 0s and 1s: 10 0s,
22 1s; chi-square = ((16 - 10)^2)/16 + ((16 - 22)^2)/16 = 4.5 with
1 d.f. From a table of chi-square, we see that the statistic would
have that high a value less than 5% of the time if the null
hypothesis were true, so we suspect that this possible PT is not
just random garbage from using a wrong key, but is likely to be a
real (redundancy-containing) PT.
There are more sensitive statistical tests, but chi-square is
explained in introductory statistics texts. In MilCryp the delta
I.C. is used instead of chi-sq, with less detail about computing
likelihoods. It's easier to understand when there are more than 2
categories of symbols, e.g. traditional ABC...XYZ instead of 01.
------------------------------
From: [EMAIL PROTECTED]=NOSPAM (Arturo)
Subject: Re: New Crypto Regulations
Date: Sun, 16 Jan 2000 17:29:38 GMT
On Fri, 14 Jan 2000 10:27:17 -0700, "John E. Kuslich"
<[EMAIL PROTECTED]> wrote:
>I hereby dare anyone to tell me that he/she has read and understood the
>new crypto regulations. They are simply beyond comprehension and
>deliberately so. These regs will make many a lawyer rich!
>
>see http://www.cdt.org/crypto/admin/000110cryptoregs.shtml
>
>What kind of government can get away with making laws the meaning of
>which are not clear until such time as one is prosecuted for violating
>such laws?
Currently, about 90% of them
------------------------------
** 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
******************************
