Cryptography-Digest Digest #16, Volume #9 Mon, 1 Feb 99 15:13:03 EST
Contents:
Re: Random numbers generator and Pentium III (R. Knauer)
Re: RNG Product Feature Poll (Mok-Kong Shen)
Re: Some more technical info on Pentium III serial number (Tommy the Terrorist)
Re: yet another U.S export restriction ques... (Kent Briggs)
Re: Truth, theoremhood, & their distinction (wtshaw)
Re: Truth, theoremhood, & their distinction (wtshaw)
Re: RNG Product Feature Poll (Terry Ritter)
Re: yet another U.S export restriction ques... (Jim Gillogly)
Re: Foiling 56-bit export limitations: example with 70-bit DES ([EMAIL PROTECTED])
AES2 Paper submission deadline (David Crick)
Java random ("Else")
Re: yet another U.S export restriction ques... (Doug Stell)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random numbers generator and Pentium III
Date: Mon, 01 Feb 1999 14:55:40 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 01 Feb 1999 15:32:46 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>I am not familiar with the book.
I recommend you become familiar with it, at least the introduction and
the first chapter. If you want to know something about randomness in
general, that is a good place to start.
>But I suspect that you misunderstood something.
That is entirely possible with a topic as complex as randomness. The
concept of randomness in general is as mysterious as Quantum Mechanics
itself.
>The assertion above 'If p<1/2, then there are only
>finite number of 1s in an infinite sequence' is obviously false.
>Counter-example: 001001001001.......... Here p=1/3<1/2. But obviously
>there are infinite 1's.
It is problem 1.10.3 on page 64 (2nd Ed.). The exact statement of the
problem is as follows:
+++++
1.10.3. [25] In an infinite sequence generated by a (p,1-p) Bernoulli
process, let An denote the event that a run of n consecutive 1s occurs
between the 2^n-th and 2^n+1-th trials. Prove that for p>=1/2, then
with probability one there occur infinitely many An; if p<1/2, then
with probability one there occur only finitely many An.
Comments: Hint: use elementary combinatorics.
+++++
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: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: RNG Product Feature Poll
Date: Mon, 01 Feb 1999 15:36:13 +0100
R. Knauer wrote:
>
> On Mon, 01 Feb 1999 08:05:08 -0600, [EMAIL PROTECTED] (Dan S. Camper) wrote:
>
> >For what it's
> >worth, both methods produced very similar results in Diehard.
>
> Insecure PRNGs can pass Diehard, but that does not make them suitable
> for the proveably secure OTP cryptosystem.
>
> You must certify the security of your generator based on its design
> and its internal performance, not its output.
>
> I am not saying that your device would fail a design analysis, just
> that relying on statistical testing of the output is a poor way to
> characterize a TRNG.
But you have so far never given a scientific method to 'characterize'
or to 'certify'.
M. K. Shen
------------------------------
From: Tommy the Terrorist <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,comp.sys.intel
Subject: Re: Some more technical info on Pentium III serial number
Date: 1 Feb 1999 13:26:40 GMT
In article <[EMAIL PROTECTED]> John Savard,
[EMAIL PROTECTED] writes:
>Because the software is protected against tampering _by the user_. So
>it will only take your real Pentium III ID number, hash it with the
>Intel-signed web site identifier of the web site you're visiting, and
>give them a personal identifier that can't be tracked but can't be
>forged.
This is what it sounded like to me: that you would have NO ACCESS
to the actual identifier, that it would work like a secret key locked
inside the chip, that you could only use to "sign" things.
However, to assume that this means it can't be tracked sounds like
a major mistake. I presume that the web site sends something
and gets back a "signed" message. They themselves won't know
who "signed" it. But any spy with access to the "signature" can
then go back and figure out which public key in their database
"signed" it. The database need only be semi secret, since it's
public keys, and if it "accidentally" got divulged to a few random
law enforcement agencies (especially in China) it wouldn't really
perturb the ones running the scheme.
After all, in American parlance, if only military, police, and secret
police can track your communications, then they are still "private"!
------------------------------
From: Kent Briggs <[EMAIL PROTECTED]>
Subject: Re: yet another U.S export restriction ques...
Date: Mon, 01 Feb 1999 17:27:41 GMT
chris wrote:
> what if i compressed the data, then ran it through a block cipher? it
> seems to me that compression (of the zlib flavor) could be seen as a
> kind of keyless stream cipher (a hash?).
Compression before encryption is allowed as long as it's documented. If you
try to invent your own compression technique, the NSA will probably ask you
for source code.
> also, i thought the approval was now automatic, in cases of 56 bits or
> less?
Nope, all encryption headed for export from the U.S. (other than to Canada)
requires a one-time review.
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: sci.math,comp.theory
Subject: Re: Truth, theoremhood, & their distinction
Date: Mon, 01 Feb 1999 10:14:22 -0600
In crypto, you find in theoremhood that a definition of an algorithm is
sufficiently complete: truth is embodied in whether the algorithm has been
fully demonstrated to function, and is described in all detail that will
enable someone else to replicate the function of it.
A theorem that one algorithm is stronger than another, resistance to
solution, depends on whether either or both can be solved and methods
compared; the only truth that can be available is dependent on the solver
delivering the secrets of solution of them, which might be elusive
information.
>
> > The only way to define the consepts of a mathematical theory is by
defining them in
> > terms of more primitive concepts.
Like programming language perhaps? In crypto, certain theories of
functionality can be demonstrated, moving theory to reality. "Mathematics
is strong, while words are very weak."
--
A much too common philosophy:
It's no fun to have power....unless you can abuse it.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: sci.math,comp.theory
Subject: Re: Truth, theoremhood, & their distinction
Date: Mon, 01 Feb 1999 10:24:14 -0600
In crypto, you find in theoremhood that a definition of an algorithm is
sufficiently complete: truth is embodied in whether the algorithm has been
fully demonstrated to function, and is described in all detail that will
enable someone else to replicate the function of it.
A theorem that one algorithm is stronger than another, resistance to
solution, depends on whether either or both can be solved and methods
compared; the only truth that can be available is dependent on the solver
delivering the secrets of solution of them, which might be elusive
information.
>
> > The only way to define the consepts of a mathematical theory is by
defining them in
> > terms of more primitive concepts.
Like programming language perhaps? In crypto, certain theories of
functionality can be demonstrated, moving theory to reality. "Mathematics
is strong, while words are very weak."
--
A much too common philosophy:
It's no fun to have power....unless you can abuse it.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: RNG Product Feature Poll
Date: Mon, 01 Feb 1999 18:19:00 GMT
On Mon, 01 Feb 1999 08:05:08 -0600, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (Dan S. Camper) wrote:
>[...]
>The data is generated a byte (8 bits) at a time. A particle detection
>interrupts the incrementing of a 16-bit register, running in the
>background. The high and low 8 bits of that register are XOR'd together
>to produce the output byte. The register is not reset between
>detections. I don't remember offhand if the register is seeded at zero
>when power is first applied or not. The device has been tuned so that the
>16-bit register cycles once (on average) between detections.
Having long thought this would be a good idea, I always assumed it was
common knowledge from the 60's. So it is with some irony and sorrow
that I propose claim 1 on page 23 of US Patent 5,627,775 granted 1997
May 6:
"We claim:
1. A circuit for generating a nonreproducible, nonperiodic
sequence of values, comprising:
a noise source;
means for generating timing signals from the noise source;
an independent free-running multistate digital circuit having a
predetermined distribution of states; and
buffering means for storing states of the digital circuit at
random times in accordance with the timing signals."
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: yet another U.S export restriction ques...
Date: Mon, 01 Feb 1999 10:30:01 -0800
Reply-To: [EMAIL PROTECTED]
chris wrote:
> also, i thought the approval was now automatic, in cases of 56 bits or
> less? i wouldn't be surprised if i was mistaken, but i remember
> reading something like this.
It's a mixed message again. At the end of BXA page dated 30 Dec 1998:
http://www.bxa.doc.gov/press/98/1230Encryption.html
Finally, the regulations eliminate the need to obtain licenses for
most encryption commodities and software up to 56-bits or equivalent
strength.
However, here's another current (31 Dec 1998) page that I think is
supposed to implement this guidance:
http://www.bxa.doc.gov/Encryption/1231ERC.htm
This creates a new license exemption category ENC which involves a great
deal of legalese-looking stuff, including this:
(ii) Eligible commodities and software. (A) Mass market and non-mass
market encryption commodities and non-mass market software having symmetric
algorithms with key lengths up to and including 56-bits, such as DES or
equivalent (such as RC2, RC4, RC5, and CAST) which are classified as a
result
of a technical review (see paragraph (c) of this section). The commodity or
software must not allow the alteration of the cryptographic functionality by
the user or any other program. Encryption chips, integrated circuits,
toolkits and executable or linkable modules are not authorized for export
under the provisions of paragraph (a)(3).
So it looks to me like BXA does want you to get an official technical review
and clearance before exporting, and that the approval is not in fact automatic.
Most importantly, <you> don't decide whether it's 56-bit and equivalent to DES
in strength: <they> do. It also looks to me like you're applying for an
export license, whether they choose to call it that or not, despite the thrust
of their press release.
Furthermore, it requires that it be implemented in software that cannot be
altered by any other software in a way that results in stronger encryption.
Hardware need not apply. Any estimates on how much software fits in this
category? I personally do not believe in tamper-proof software, but perhaps
BXA is more up on this than I. (That latter bit was sarcasm, by the way.)
A personal story: I asked BXA for permission to post my Enigma source to
mailing lists and Web pages, since I wanted to share with colleagues in
Britain, Switzerland and France (and presumably elsewhere) who have helped
me with my research, as well as give future students of Enigma a kick start.
They reviewed it (in a timely fashion, I hasten to add), and I was told I
needed to apply for an export license and name all the people ("end users")
who were going to be receiving it. I'd made it clear that we were discussing
classical WW2 Wehrmacht and Naval Enigma, the ones broken 60 years ago by the
Poles and other Allies, rather than some wonderful modern unbreakable system
of the same name. Sigh. I dropped it. I'll check again when President
Ventura is sworn in.
--
Jim Gillogly
Highday, 11 Solmath S.R. 1999, 17:48
12.19.5.16.6, 13 Cimi 19 Muan, Second Lord of Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Foiling 56-bit export limitations: example with 70-bit DES
Date: Mon, 01 Feb 1999 18:31:45 GMT
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?
[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).
[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.
[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?
[snip]
> 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.
--
Peter
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
Date: Mon, 01 Feb 1999 19:02:15 +0000
From: David Crick <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: AES2 Paper submission deadline
AES2 Paper submission deadline is today - Feb 1, 1999 (see
http://csrc.nist.gov/encryption/aes/round1/conf2/aes2cfp.htm).
I presume various parties from here are submitting to this?
Will we have to wait for NIST to publish them or will they be
going up on the web sites soon?
Just wondering,
David.
--
+---------------------------------------------------------------------+
| David Crick [EMAIL PROTECTED] http://members.tripod.com/~vidcad/ |
| Damon Hill WC '96 Tribute: http://www.geocities.com/MotorCity/4236/ |
| Brundle Quotes Page: http://members.tripod.com/~vidcad/martin_b.htm |
| PGP Public Key: (RSA) 0x22D5C7A9 00252D3E4FDECAB3 F9842264F64303EC |
+---------------------------------------------------------------------+
------------------------------
From: "Else" <[EMAIL PROTECTED]>
Subject: Java random
Date: Mon, 1 Feb 1999 22:12:52 +0300
Please comment on this scheme of generating random number in Java:
seed instance of Random as
Random rnd = new Random( System.currentTimeMillis() ^ (new
Object().hashCode() << 16) );
then
for( int i=0;i<n;i++ )
rnd = rnd.nextInt( );
where n is a number of times one thread runs while another one sleeps for
100 ms. It's in the range of 90,000 - 150,000 on my machine.
then I get the random sequence of 16 bytes which I use to generate RC4 key.
This method is some what different from SecureRandom. I can't use
SecureRandom because takes too much time - over 1 second.
Any suggestions of improvement? Any visible vulnerabilities?
Thanks.
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: yet another U.S export restriction ques...
Date: Mon, 01 Feb 1999 19:40:49 GMT
On Mon, 01 Feb 1999 10:30:01 -0800, Jim Gillogly <[EMAIL PROTECTED]> wrote:
>So it looks to me like BXA does want you to get an official technical review
>and clearance before exporting, and that the approval is not in fact automatic.
>Most importantly, <you> don't decide whether it's 56-bit and equivalent to DES
>in strength: <they> do. It also looks to me like you're applying for an
>export license, whether they choose to call it that or not, despite the thrust
>of their press release.
Essentially, this is correct, although there are different ways of
looking at it. BTW, you may have noticed that, once again, the new
regulations give you more streamlined process, rather than significant
relaxation of the rules.
1) To get an exemption, they want to know that you have followed the
<their> rules.
2) They want the technical info to attack your system when and if they
need to and to do so without having to alert you or chase you down.
This is one way to get that info up front. (I've written such product
disclosures in a previous life.)
3) If you get an exemption, i.e., a blanked approval, licenses for
individual exportations are not needed. Otherwise, they are. That's a
big difference.
>Furthermore, it requires that it be implemented in software that cannot be
>altered by any other software in a way that results in stronger encryption.
>Hardware need not apply. Any estimates on how much software fits in this
>category? I personally do not believe in tamper-proof software, but perhaps
>BXA is more up on this than I. (That latter bit was sarcasm, by the way.)
Believe it or not, they have softened in this area. All they care
about is that stronger encryption can not be easily substituted or
this encryption used for non-approvel purposes - by the average
person, using commonly available knowledge and tools. They know that
they can't make software tamper-proof against an expert with a
disassembler and have given up trying to do so.
>A personal story: I asked BXA for permission to post my Enigma source to
>mailing lists and Web pages, since I wanted to share with colleagues in
>Britain, Switzerland and France (and presumably elsewhere) who have helped
>me with my research, as well as give future students of Enigma a kick start.
>They reviewed it (in a timely fashion, I hasten to add), and I was told I
>needed to apply for an export license and name all the people ("end users")
>who were going to be receiving it.
The killer word here is "source."
> I'll check again when President Ventura is sworn in.
Don't hold your breath. Things have relaxed slowly and under great
pressure under all the presidents that have been in office during my
20 years in the field. Whoever is in the office will get the
classified "our boys' blood in the sand" briefing and made a believer.
Actually, the biggest advances came under Bush, IMHO. All advances
came only as the result of constant and intense pressure from
industry.
------------------------------
** 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
******************************
