Cryptography-Digest Digest #22, Volume #9 Tue, 2 Feb 99 15:13:03 EST
Contents:
Re: RNG Product Feature Poll (R. Knauer)
Re: irrational idea continued (John Savard)
Re: Historical basis for BLOWFISH (John Savard)
Re: What's the newest on MD4? (Gregory G Rose)
Re: RNG Product Feature Poll ("Tony T. Warnock")
Re: Who will win in AES contest ?? (Thomas Pornin)
ANSI X9.17 (Vladimir Beker)
Re: Metaphysics Of Randomness ("John Feth")
Re: Historical basis for BLOWFISH ("karl malbrain")
Re: Foiling 56-bit export limitations: example with 70-bit DES
([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: RNG Product Feature Poll
Date: Tue, 02 Feb 1999 17:03:47 GMT
Reply-To: [EMAIL PROTECTED]
On 2 Feb 1999 10:27:58 -0500, [EMAIL PROTECTED] (Herman Rubin)
wrote:
>The time at which one radioactive decay occurs can affect whether
>another is even detected. This makes the detection times AT BEST
>a renewal process, and it can be even worse.
Since the occurance of any decay event is indeterminant in time (that
means there is no way to know in advance when it will occur), the
detection of any decay event is also indeterminant in time. Knowing
that the detection of a decay event will not occur during a particular
interval of time does not mean you know when one will occur later.
Imagine that you set up the detector to detect one event, shut it off
for a week and then turn it back on. The next decay event which you
detect will be completely indeterminant in time, having nothing to do
with the fact that no events were detected earlier. The fact that the
detector was turned off does not determine when the next decay event
will be detected after turning the detector back on.
>If by completely random in time, you mean a Poisson process, the answer
>is no.
I am using the strong crypto definition of random, not the statistical
definition. In fact, that is what this whole discussion is about. I
maintain that statistical descriptions of events are inadequate to
characterize crypto-grade randomness, which is suitable for use in the
OTP system.
>If one uses an analog-threshhold detector, it can get quite
>complicated, and not even be a renewal process. That is, the times
>between detections may not even be independent.
The time between detections will always be indeterminant. Saying that
you know that the detection of a decay event cannot occur during a
particular interval does not mean you can say that when a detection
does occur.
Consider 4 times:
t1, the time when a first decay is detected;
t2, the time when a decay first cannot be detected;
t3, the time when a decay can first be detected;
t4, the time when a decay is secondly detected.
The interval during which no detection can occur is t2 -> t3.
The detection of a second decay event at t4 is in no way determined by
t2, t3, or t3-t2. That is, the value if t4 cannot be known even though
it is known that it is not any time between t2 and t3.
If the interval of non-detection could cause you to know when a
detection CAN occur, then the decay process would not be
indeterminant.
Kolmogorov algorithmic complexity theory addresses this issue (see Li
and Vitanyi, op. cit.). If you have a random process x1, followed by a
non-random process x2, followed by a random process x3, then the
overall process is represented by x = x1 . x2 . x3, where the dot
operator means algorithmic concatenation.
Here x1 is the detection of the first decay event, x2 is the
non-detection of decay events for a specified interval, and x3 is the
detection of a subsequent event after that interval.
The algorithmic complexity of x, K(x), for the overall process is not
significantly reduced by the inclusion of the non-random process x2.
IOW, your certainty that no decay event can be detected in the
blanking interval, t2 -> t3, does not effect the randomness
(indeterminancy) of detection of a second detection after that
interval.
>I have just looked at this; the numbers should be reasonably good, but
>not that good. One problem is that of measuring the time; this can
>be seen to produce biases and failure of independence on the order of
>10^{-4}. This should not be a problem for cryptography, but would be
>for statistical use.
I do not understand what you just said. You seem to be agreeing with
me that statistical randomness has no impact on crypto-grade
randomness.
Also I do not see how the measurement technique employed in HotBits
results in bias, much less how you managed to quantify it with a
number such as 10^{-4}.
Please elaborate on all these issues.
>There is always Murphy's Law to worry about. One might barely be
>able to test at a high enough level for cryptographic use, but
>this would not be good enough for statistical use, where 10^10
>to 10^15 bits are commonly used now.
Statistical tests for TRNGs are useless. If one cannot generate
crypto-grade random numbers algorithmically, then one cannot test
crypto-grade randomness algorithmically, otherwise one could generate
such numbers algorithmically by a simple filtering scheme.
A TRNG must be capable of generating all possible sequences of a given
finite length equiprobably, therefore its output cannot be filtered in
any way. Each of the 2^N sequences of length N must be output
equiprobably, or the complete indeterminancy of the TRNG is destroyed,
and proveable security cannot be achieved.
Only by conducting a careful design audit of the TRNG itself can one
certify that it is proveably secure. That audit includes testing the
subsystems that make up the TRNG, not its output. Testing the output
results in creating a bogus distribution of "good" and "bad" strings,
which violates the specification for a TRNG, namely that it be capable
of outputting *ALL* possible strings, not just "good" ones based on
some statistical notion of what constitutes "good" or "bad" strings.
If a TRNG is not capable of generating all possible strings
equiprobably, it is not a TRNG for purposes of secure crypto.
Bob Knauer
"Sometimes it is said that man cannot be trusted with the government
of himself. Can he, then, be trusted with the government of others?"
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: irrational idea continued
Date: Tue, 02 Feb 1999 19:11:01 GMT
[EMAIL PROTECTED] (Gregory G Rose) wrote, in part:
>1. a^b, where a is an integer > 1 and b is a
>"quadratic irrational" (ie. a square root).
>2^sqrt(2), for example, is such a transcendental.
That is interesting - that cryptographic weaknesses have been found in
the decimal expansions of some types of number, but something like
437^sqrt(5) would be stronger.
However, the other objections to this scheme in practice are still
present: the fact that some serious research has been done on some
aspects of this method of encryption may produce results useful for
other purposes, but I don't think it should give anyone the idea that
this is a good method of encryption, even if it might potentially be
secure under some conditions that are now better understood.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Historical basis for BLOWFISH
Date: Tue, 02 Feb 1999 19:19:11 GMT
karl_m <[EMAIL PROTECTED]> wrote, in part:
>Are
>S-BOXES in fact a proven non-linear means of KEY scheduling?
It certainly is true that the function of n, f(n) = the n-th digit of
pi, is for most ranges of n a non-linear function.
As Bruce pointed out, no one has heard of an "early" version of
Blowfish that was linear. Blowfish deliberatly used a very slow method
of key scheduling - and one that, although not provably secure, like
every other method, was of _excellent_ quality compared to the methods
of key scheduling used up to then, and that was true right from the
very beginning.
A provably secure key schedule? You've given me an idea! *Someone* is
going to suggest, sooner or later, the use of Blum-Blum-Shub to
generate the subkeys for a block cipher, so I may as well do it now
and save them the trouble.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: What's the newest on MD4?
Date: 2 Feb 1999 11:23:53 -0800
In article <[EMAIL PROTECTED]>,
Mr. Anssi Bragge <[EMAIL PROTECTED]> wrote:
> What's the situation with MD4 now? Everyone seems to be
>talking only about MD5 on daily basis.
Hans Dobbertin's paper demolishing MD4 was
published a month or two ago in the Journal of
Cryptology, although the result has been known for
a couple of years. While MD5 has not been
"demolished", it is certainly suspect.
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: RNG Product Feature Poll
Date: Tue, 02 Feb 1999 10:38:37 -0700
Reply-To: [EMAIL PROTECTED]
R. Knauer wrote:
> Since the occurance of any decay event is indeterminant in time (that
> means there is no way to know in advance when it will occur), the
> detection of any decay event is also indeterminant in time.
This doesn't follow. The characteristics of the detector are also important.
Tony
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: Who will win in AES contest ??
Date: 2 Feb 1999 17:04:33 GMT
According to Hironobu Suzuki <[EMAIL PROTECTED]>:
> For example, Linux is running not only under Intel CPU but also
> running under PPC, SPARC, Alpha, MIPS etc.
But some time-critical things use (when available) a highly optimized
asm implementation. In Linux, about everything is I/O or memory bound,
and a good C implementation is just what is needed. But, for an encrypted
filesystem, you really want the most optimized cipher you may find.
Think about the IP checksum code: in order to implement very high
network bandwidth, the checksum calculation must be as optimized as
possible. All ports (except the Alpha) include an assembly version
of this function.
Same would apply to an encrypted filesystem: a generic C version,
for development and exotic architectures, and hand-optimized
assembly-powered versions for some architectures.
> BTW. I have a question about serpent asm code which you tested. Is
> this serpent code optimized using the right way of bit slice
> technique?
Without the bitslice technique, Serpent itself would make little sense,
and it would run slower than a snail.
--Thomas Pornin
------------------------------
Date: Tue, 02 Feb 1999 19:00:25 +0200
From: Vladimir Beker <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc
Subject: ANSI X9.17
Does somebody know how to reach the text of ANSI X9.17 standard?
Vladimir
------------------------------
From: "John Feth" <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: 2 Feb 1999 19:41:28 GMT
R. Knauer <[EMAIL PROTECTED]> wrote in article
<[EMAIL PROTECTED]>...
> On 29 Jan 1999 20:36:26 GMT, "John Feth" <[EMAIL PROTECTED]>
> wrote:
Bob, I snipped a bunch of stuff out of here. You will remenber that you
had just written "All (finite) numbers are liars.":-) My comments are
below
>
> >Golly Bob, you'll be even happier if you look at numbers as strings of
> >digits. Then you'll find that the longer the string the more you know
> >about the randomness of the sequence, and you can test any old finite
> >string to see if it is lying to you.
>
> But such tests do not result in proveably security, which is required
> by the OTP system. True randomness is necessary for proveable
> security. Statistical testing does not measure proveable security.
>
> Tell us which of these unskewed numbers is truly random.
>
> 1) 10101010
>
> 2) 01110010
>
> Your statistical tests will reject the first one and accept the second
> one. Yet the first one was produced by a TRNG, and the second one was
> produced by a PRNG. If you rejected #1, you discarded a perfectly good
> TRNG. If you accepted #2, your ciphers would be trivially insecure.
>
> The fact is that your statistical tests do not tell you enough to make
> the correct decision regarding proveable security, and worse than
> that, they can cause you to be deceived. If a random number generator
> slips past your statistical tests, you could be vulnerable to
> cryptanalytic attack and not even know it.
>
> Having your ciphers broken trivially is the surest way I know to wipe
> that smug look off your face in a hurry.
>
> Bob Knauer
>
Jumpin' Jehoshaphats Bob, since I want you to think I'm right and not smug
(my mom would just hate that!), I'm going to remind you just one more time
that dividing random strings into True Random Numbers and Pseudo Random
Numbers creates a distinction without a difference since no test exists to
distinguish them.
But that's not enough. I want to get beyond the sophistry that creates
distinctions without differences. I'm going to give you a method to create
reams of certifiable radom strings whenever you want. You can use them
however you wish; send them to friends who would appreciate them, use them
for one time pads, read them out loud, heck Bob, you could even run a
statistical analysis on them if you want to.
OK, here goes. Find two large primes, p and q such that the product is
1500 digits long. Find a number, e, that does not divide the product
(p-1)*(q-1) evenly. Now we're in business. Generate your first random
string, c, as
c=mod(m^e, p*q)
by choosing m to be a non-zero number 1490 digits long. Change a single
digit in m and you have an entirely different string c. You can continue
in this manner and concatenate the subsequent strings to create an even
larger random string. Just think of it Bob, any string m, pathological,
ordered, internally correlated or however special is turned into a randomly
sequenced string by this operation. Our cup runneth over!
The good news is that you don't even have to take my word for it; I
confess, this algorithm didn't originate with me (how am I doing on that
smugness thing, eh?). It has been studied a lot in cryptographic circles.
All of the claims I have made about the algorithm output have been made
before and lead to an encryption method based on this algorithm.
By the way Bob, for epistemological reasons you can choose to discard p, q,
p-1, and q-1, keeping only the product p*q and e. This will keep even your
own mind unsullied by the thought that anyone could find d such that
m=mod(c^d,p*q) and somehow harm you. Pretty cool, que no?
Regards,
John Feth
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: Historical basis for BLOWFISH
Date: Tue, 2 Feb 1999 11:54:45 -0800
John Savard <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>As Bruce pointed out, no one has heard of an "early" version of
>Blowfish that was linear. Blowfish deliberatly used a very slow method
>of key scheduling
My question is the 1993 choice of S-BOXES in light of the up and coming
application of LINEAR analysis to cryptography -- normalizing the system of
linear equations generated by Plain texts against Cypher texts to produce
the key schedule.
How does <<very slow method>> apply? Karl M
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Foiling 56-bit export limitations: example with 70-bit DES
Date: Tue, 02 Feb 1999 19:09:21 GMT
In article <794ruh$a7k$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <78t64b$61o$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > In article <78ss2c$s4b$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] wrote:
> [snip]
> > > Have you considered doing both (i.e., Ci = rndblock_X XOR DES(Pi XOR
> > > rndblock_X), where rndblock_X is the block you chose out of 2^M blocks)?
> > >
> >
> > Yes, but it is worse.
>
> Why?
Because if the plaintext is encrypted with an unknown-key (the choice I am
considering) then the intended recipient will gain less in comparison to the
attacker.
>
> [snip]
> > > This brings up another question. You have the underlying assumption that
> any
> > > 56-bit algorithm is automatically exportable. From the U.S., this is not
> true
> > > (I don't know about other Wassenaar countries).
> >
> > Interesting subquestion.
> >
> > To the question itself, no. My assumptions were not what you say. I assumed:
> > (i) DES is automatically exportable from the US and, (ii) DES is a 56-bit
> > cipher. Both are true.
>
> Multiple encryption is, in general, not allowed in products being exported
> from the U.S. I don't think they'd make an exception for you based on the
> argument that "the key for the post-encryption is never sent, so the
> recipient has to brute-force the additional M bits." They would see only the
> other part of the equation ("we have to brute-force 56+M bits"), and they
> would classify you as controlled cryptograpy (not mass-market exportable).
1. That is not what WA says -- it is the amount of secret-key that is
controlled. And, M-DES only defines a secret-key that is 56-bit wide Please
read the WA.
2. Further, in use, no one can say M-DES ciphertext is not DES -- unless they
admit they tried to break it.
> [snip]
> > This assumption is only granted if "they" have broken the whole 70-bit key
--
> > not otherwise. In other words, what you mention is not possible **if** the
> > *whole* 70-bit key is not broken -- thus, it cannot be used to break any bit
> > of that key. That is why I said before (above): "No, it is not less secure."
>
> If Bob sends the same message twice (or a message with at least one block the
> same as in a previous message, say some header information), and he uses the
> same DES key, but a different "whitener_block", then an attacker can derive
> whitener_block1 XOR whitener_block2, and greatly shorten his search. If,
> instead of XORing the DES ciphertext with one of 2^M blocks, you had
> encrypted the DES ciphertext with, say, RC2 using an M-bit key, this shortcut
> would not be available.
Please read the text -- this is described there, and will not work as you say
for two reasons:
1. Different messages should negotiate different DES keys -- there is no
shortage of them ;-) -- even though they can keep the same unknown-key (now,
known to both).
2. Of course, M-DES can use RC4, RC5 or whatever you want. The use of XOR was
an example to show that nothing much more was *needed* if the assumptions are
respected. In simplicity lies understanding and truth ;-)
> [snip]
> > No, the protocol is not modified -- Bob has to inform Alice (in plain) what
M
> > he is using. One particular case is M = 0. Thus, when Bob negotiates a
cipher
> > with Alice, he sends (suppose):
> >
> > M_DES_M0 --> which means M-DES with M=0
> >
> > or
> >
> > M_DES_M14 --> M-DES with M=14
> >
> > OK?
>
> Now Bob has to send some additional info to Alice (e.g., M_DES_M0). This is a
> change to any existing protocols, isn't it?
Please don't try to inflate a simple statement ;-)
The key-negotiation protocol is the same -- the message changes a tad bit.
> > Yes -- that information never leaves Bob's machine unless XOR-encrypted with
> > the M-bit key he has chosen. Note that the known-ciphertext is now:
> >
> > (M-bit key) XOR DES(Key,Message)
> >
> > and NOT just DES(Key,Message).
> >
> > This is a rather funny reverse use of XOR, because the key is fixed and
> > the plaintext (here, DES(Key,Message)) is random ;-)
>
> Not if Bob sends a message containing some blocks that are the same as in
> some previous message, and Bob uses the same DES key for both messages.
>
> --
I must ask again, as I dis two msgs ago -- did you read the paper? This is
discussed, along with other possibilities. The cure is simple -- change DES
session-key for each message -- there is no shortage of them. As another
cure, you can change the unknow key. Or, even, change BOTH, as the text
recomemnds, if your security needs so justify.
Cheers,
Ed Gerck
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
