Cryptography-Digest Digest #901, Volume #10 Thu, 13 Jan 00 23:13:01 EST
Contents:
Re: frequency analysis (James Pate Williams, Jr.)
Re: Simple Encryption ... (Dan Day)
Re: "1:1 adaptive huffman compression" doesn't work (Tim Tyler)
Re: Intel 82802 Random Number Generator (David Hopwood)
Re: "1:1 adaptive huffman compression" doesn't work (Tim Tyler)
Re: Blum, Blum, Shub generator (Tim Tyler)
ARC4 discussion? ("r.e.s.")
Re: Blum, Blum, Shub generator (Thierry Moreau)
Re: simple block ciphers (David Wagner)
encryption/decryption programs (Tim and Carolyn)
Re: Random numbers generator ("Douglas A. Gwyn")
Re: UK Government challenge? ("Douglas A. Gwyn")
Re: frequency analysis ("Douglas A. Gwyn")
Re: Questions about message digest functions ([EMAIL PROTECTED])
Re: AES & satellite example ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: frequency analysis
Date: Fri, 14 Jan 2000 01:24:43 GMT
On 13 Jan 2000 23:00:14 GMT, Jimmy Ross <[EMAIL PROTECTED]> wrote:
>Does anyone know where I can find the relative frequencies of the
>characters of the English alphabet in English text?
>
>Thanks,
>Jimmy
Table 1.1 in _Cryptography: Theory and Practice_ by Dougles R. Stinson
page 26.
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: Simple Encryption ...
Date: Fri, 14 Jan 2000 01:44:14 GMT
On Wed, 12 Jan 2000 19:27:46 -0800, "r.e.s." <[EMAIL PROTECTED]> wrote:
>I get
>2^64 bits = 2^31 gigabytes = 2147483648 gigabytes.
Oops, I (obviously) read "bytes" for "bits".
Dang, that's *twice* this week I've misread something on
sci.crypt and then posted something about it. Time to get my glasses
checked, it would seem.
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: "1:1 adaptive huffman compression" doesn't work
Reply-To: [EMAIL PROTECTED]
Date: Fri, 14 Jan 2000 01:14:47 GMT
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.
------------------------------
Date: Thu, 13 Jan 2000 05:54:35 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Intel 82802 Random Number Generator
=====BEGIN PGP SIGNED MESSAGE=====
Guy Macon wrote:
>
> (Discussing paper at
> ftp://download.intel.com/design/security/rng/CRIwp.pdf )
>
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> (Scott Nelson) wrote:
> >
> >The input bits to the Von Nuemann rejector are correlated.
> >Correlation can range anywhere from a minor annoyance
> >to a major problem.
>
> If (questionable assumption!) the *only* bias was an adjacent
> bit correlation of the input bits to the Von Nuemann rejector,
> the output bits would be unbiased.
That's not correct. An input that alternates between 0 and 1
will produce an output from the rejector containing long (or
at least longer than expected) stretches of 0s or 1s.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOH1obzkCAxeYt5gVAQGbIQgAjU4eb5QmpCmHFp5feO/zJMkBmIibwHLt
sPJAzRDinz29o/S/Xyqbmquz9Pu406pdbhKoWrDIA6bREYu45BPKTaZ4dPsOFJw+
ZHpmgA7FoYl6cR1YMtorFSQcqNpTI62llr8D4Bn722LuRsgnq/PhCp530t2/6i3f
UWy3kqXmMeCL6FWbaNJLxHedcO1QGH7OvLmuG7eNXR2XkVQyAzcAGZsSMFxJHric
ICkM3g0FYdAql1Pl5ADrVKvx4PAWp8fUcQJ93HQ1uipL9anNS8eILCOXy7Rci5ER
4fG8TTMeAqNFdwNAQK4G/PQyTRv+gxQBOGuzefS086t+9Iyfo3bAhg==
=rYDV
=====END PGP SIGNATURE=====
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: "1:1 adaptive huffman compression" doesn't work
Reply-To: [EMAIL PROTECTED]
Date: Fri, 14 Jan 2000 01:28:00 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: My proposal is able to satisfy the requirement you
: originally raised, i.e. to give the analyst no information via
: the decompression-(re-)compression process.
Which it would do reasonably well, /if/ you could get hold of some "real"
random numbers. Getting hold of them in a portable way would be better
still.
: Hence, if that is implemented, then there is no necessity to spend time
: and energy to develop 1-1 software of the sort that you have done.
Unless you want theoretical perfection - rather than a non-derterministic
compressor, whose security depends partly on a supposedly random process.
One additional positive thing about 1-1 compressors is that you can
mechanically verify that the rest of the compression program (besides the
ending scheme) is acting in the correct 1-1 manner - by testing lots of
files.
Also, the resulting files are shorter ;-)
: And further I am of the opinion that the benefit of having that
: software isn't worth the time and energy you and others have spent
: in developing the software.
Don't mince words. Say what you /really/ mean ;-)
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Where there's a will, there's an inheritance tax.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Blum, Blum, Shub generator
Reply-To: [EMAIL PROTECTED]
Date: Fri, 14 Jan 2000 01:41:18 GMT
lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote:
: Every time this topic comes up, there is incredible misinformation spewed.
:-(
: Choose BBS as a good RSA modulus, with p and q congruent to 3 mod 4.
: Choose a random x, and start with x_0 = x^2. That's all you need to do.
x = 1 ;-)
: Concerns about cycle lengths are misplaced. [...]
: Therefore, it follows from the RSA assumption that finding short cycles
: is impossible, for moduli large enough that factorization is intractable.
I /think/ you have "difficult" and "impossible" muddled up here...?
There are guaranteed to be short cycles...
: The advice to choose moduli with guaranteed long cycles, and to choose
: seeds that way, is completely useless.
Without this it appears that you don't get the "proven" security discussed
in the original work. You wind up with a finite change of getting a rather
weak stream of data.
I thought the "proven security" was a BBS selling point. Should your
algorithm still be described as BBS if it uses a different set of
constraints on the primes?
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Jesus saves. Immanuel Kant.
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: ARC4 discussion?
Date: Thu, 13 Jan 2000 18:31:43 -0800
Would it be appropriate, in this NG, to
discuss details of the ARC4 algorithm ?
-- r.e.s. [EMAIL PROTECTED]
------------------------------
From: Thierry Moreau <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Blum, Blum, Shub generator
Date: Thu, 13 Jan 2000 21:47:30 -0500
lcs Mixmaster Remailer wrote a very interested post, to which I
definitely agree:
>
> Every time this topic comes up, there is incredible misinformation spewed.
>
> ... interesting stuff ...
>
> Concerns about cycle lengths are misplaced.
> ...
>
> It is like the advice you used to hear to choose "strong" RSA moduli by careful
>choice of p and q.
> No one does this any more, because it has been proven to be pointless.
> ...
>
> Worry about cycle lengths is nothing more or less than superstition.
>
> And don't get me started on checking that x is not a multiple of p or q...
> ;-)
The information I posted was in response to a post related to small
number BBS, much like a toy example to understand the basic maths.
When modulus sizes grow to cryptographic strength, your educated piece
of advice is to be followed.
Thanks for this post. I strongly suspected that the scientific knowledge
about the RSA modulus selection was a strong counter-argument against
restricting BBS modulus to special primes (for large modulus sizes) but
I couldn't express this as well as you did.
- Thierry Moreau
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: simple block ciphers
Date: 13 Jan 2000 18:49:41 -0800
In article <858np6$dee$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <8582sl$72i$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (David Wagner) wrote:
> > There's a chosen-plaintext/ciphertext attack that recovers p:
> > Pick a random z>p. [...]
>
> z = random no, >p ... but z has to be less then p. In my example you
> can only encrypt 64 bit values [under a 72 bit p) so this can never
> happend.
Ok, so in this case the chosen-plaintext/ciphertext attack doesn't work
in this setting.
But see my followup post for a second attack, chosen-plaintext this time,
that does seem to work even in your setting.
------------------------------
Date: Thu, 13 Jan 2000 21:55:56 -0500
From: Tim and Carolyn <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.labview
Subject: encryption/decryption programs
Hello,
Lately I've been reading a fascinating book by David Kahn called the
"Codebreakers", and decided to try my hand at it. I wrote a little
LabVIEW program that can encrypt text or binary files and save it to a
new file. Files can be multiply encrypted with different passwords.
There is also a decryption program.
Is it any good? Beats me. I'm not a cryptanalyst. However, it was fun
to work on over the break. The software can be found on my Web site at
(diagrams are removed so you can't peek at my code):
http://www.cs.wcupa.edu/~tstarn/software.html
Cheers,
TKS
Oh yes, I also have a character frequency counter that I meant to
include. I'll upload it soon. In the meantime, here's an encrypted sample:
51194 50679 50183 49486 48933 48409 47831
54560 53891 53421 52734 52118 51492 50795
60906 60142 59553 58850 58078 57404 56734
51215 50712 49982 49478 48906 48327 47683
69042 68260 67499 66714 65942 65162 64366
38569 38095 37788 37320 36808 36395 36034
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Random numbers generator
Date: Fri, 14 Jan 2000 03:00:10 GMT
Simone Molendini wrote:
> C rand() routine seems me to be a weak one: it has only a 32768 cycle (it
> seems me).
The example implementation found in the 1989 C standard has a period
of 2^32, as I recall. I've seen it misimplemented (e.g. on some BSD
UNIX systems) such that it has worse properties, but for a generator
of that general class (affine multiplicative) it is a good one. For
some applications it suffices; for others, it doesn't. That is true
of any pseudo-random number generator.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: UK Government challenge?
Date: Fri, 14 Jan 2000 03:03:42 GMT
John Savard wrote:
> Their site must be busy...
The actual GCHQ challenge starts at
http://www.gchq.gov.uk/challenge.html
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: frequency analysis
Date: Fri, 14 Jan 2000 03:08:47 GMT
Jimmy Ross wrote:
> Does anyone know where I can find the relative frequencies of the
> characters of the English alphabet in English text?
What parent population did you have in mind?
The best thing is to collect your own statistics on a corpus
representative of what your application will be dealing with.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Questions about message digest functions
Date: Fri, 14 Jan 2000 02:58:42 GMT
Tim Tyler wrote
> [EMAIL PROTECTED] wrote:
> : Tim Tyler wrote
> :> Domain: possible hash values corresponding to plausible messages;
> :> Range: the frequency of the occurrences of each hash value.
>
> : Ah - there's the problem.
>
> : Given the function
> : f(x) = number of messages m (of some limited
> : length) such that x=hash(m)
> : I agree a hash is bad if f(x) is bell-shaped.
>
> : But you are simply wrong: it is _not_ expected to be
> : bell-shaped for a random function. You can test it for
> : small ranges. You'll find the graph is jagged but stays at
> : roughly the same height.
>
> This is a point mainly concerned with terminology.
The major point is not terminology; even after you shuffle
the domain as described below, you do not get a bell-shape.
There may also be a terminology problem, which is why I
tried to be so precise in asking "what random variable you
think to have a bell-shaped distribution".
> First I need to say that I have been misleading -
> for which I am sorry.
>
> I am imagining the domain to be sorted by hash frequency. I did not
> say this explicitly - which is probably a cause of misunderstanding.
>
> The curve may perhaps more accurately be described as a
half-bell-shaped
> curve.
So now you've rearranged the domain, and now it's not
bell-shaped, it's "half-bell-shaped". What's worse, that's
still false.
> A bell shaped curve does not /have/ to have a tail that
> extends to infinity.
Right, but no one suggested the lack of tails is any
problem.
> A section of a bell-shaped curve
> is still properly described as a bell shaped curve.
Only a curve that is bell-shaped is properly described as a
bell-shaped curve.
> Also - if it helps clarify things - only half a bell-shaped curve is
> present. You can sort the domain to put the centre of the bell-shaped
> curve in the middle of the domain if you're in the mood.
The issue is not clarity - you are simply wrong. If we sort
the domain so that the higher frequencies are closer to the
center, then the shape we get is something like a set
bracket, '{', turned 90 degrees clockwise. The slope is
steep at the both ends and also steep very near the center,
but shallow elsewhere. The curve height is near the medium
value for the vast majority of the area covered.
The bell-curve is the opposite. The slope is shallow at the
ends and middle, and most of the area is under the curve
when the curve height is near its maximum.
This is not a minor issue. A bell-curve would imply a
strong tendency for the digests to group together. The
set-brace-curve tells us that digests are distributed
nearly evenly. Very few digests have significantly
more or fewer preimages than the mean.
> Given all this - which undoubtedly I should have made clearer - the
> frequency distribution *is* expected to be a bell-shaped curve for a
> random function.
In my previous post I suggest testing the
distribution using modest values. One hundred
possible digests values with an average of 50
preimages each should be enough. So does it
look like a bell or a sideways set-brace?
> Finding that the frequency graph is roughly the same height does
> *not* demonstrate it approximates a linear function.
I don't follow. What does "linear function" have to do with
any issue here?
[...]
> : For messages of arbitrary size, the graph you named looses its
> : jaggedness; it becomes the flat line you want and not the
> : bell you thought.
>
> _Precisely_ the source of my objection. *Nobody* *ever* deals with
> messages of arbirary size. The /vast/ majority of such messages take
up
> more bits of information than there are atoms in the visible universe.
In theory we have to resist collisions of all sizes, in
which case a random function is perfect. In practice we
have to resist collisions of one kilobyte messages, (among
others) and increasing the brute-force work factor by one
part in 2^4000 is, in practice, no difference at all.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: AES & satellite example
Date: Fri, 14 Jan 2000 03:13:57 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Terry Ritter) wrote:
> Since we cannot know cipher strength, ...
The gubmnt is also not certain about the safety of prozac,
ritalin, carbon emissions, MTBE, cell phones, gene-altered
vegetables, guns, crypto exports, etc. Life goes on.
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
******************************
