Cryptography-Digest Digest #79, Volume #12 Wed, 21 Jun 00 17:13:01 EDT
Contents:
Re: mother PRNG - input requested ("Joseph Ashwood")
Re: Encryption on missing hard-drives ("Douglas A. Gwyn")
Re: Is this a HOAX or RSA is REALLY broken?!? (Anton Stiglic)
Re: Generating Keys for 3DES (Anton Stiglic)
Re: Encryption on missing hard-drives ("Trevor L. Jackson, III")
Re: Standards for Internet Banking (DJohn37050)
Re: Blum-Williams integer???? (Bryan Olson)
CRC-64 and 128 - Generator Polynomials? ("Ken Christensen")
Papers Accepted for SAC 2000 (Stafford Tavares)
Missing Info in the crypto-gram of MR BS (SCOTT19U.ZIP_GUY)
Re: Encryption on missing hard-drives ([EMAIL PROTECTED])
Re: Encryption on missing hard-drives (Mike Andrews)
Re: small subgroups in Blum Blum Shub (Doug Kuhlman)
Re: Missing Info in the crypto-gram of MR BS (James Felling)
Quick Question on Primitive Elements GF(p) (Simon Johnson)
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: mother PRNG - input requested
Date: Wed, 21 Jun 2000 11:09:05 -0700
> I think you're assuming something like the internal state is the size of
> the seed - and that the entire internal state is output at each step.
I was assuming nothing of the kind, I was assuming that the streams I gave
originally were complete stream from the beginning to the end of one
complete cycle of the internal data.
>
> This need not be the case - and obviously the former can't possibly be the
> case if the generator has a seed of only 2^32 - yet offers some stupendous
> period.
You statement makes no sense in terms of what was being discussed. It makes
no difference how big the seed is to the analysis that I was doing, the only
matter was the period, which I thought I was being quite clear was 12 and 6
in my examples.
>
> If seed is only 32-bit, you re-key for each message and your messages
> aren't ever very long, having a minimum period much longer than 2^32
> seems rather pointless.
Unless there is a detectable sub-period occurance, say 17 shows up every
10th byte, even though the period is 2^1234567890 makes little difference to
that 10 byte sub-period. Just simply making assumptions on the generator
based on it's period is useful on some occassions, but there are further
tests and other methods of attack than simply waiting for the period of the
generator to run out.
Joe
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Encryption on missing hard-drives
Date: Wed, 21 Jun 2000 17:38:01 GMT
[EMAIL PROTECTED] wrote:
> The reason it's only secret is partly because it needs to be accesible
> to NEST members, ...
I know that agencies often do that sort of thing, but the official
regulations require that classification (UNCLASSIFIED, CONFIDENTIAL,
SECRET, TOP SECRET) be based only on the likely level of damage to
national security should the information fall into the wrong hands.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Is this a HOAX or RSA is REALLY broken?!?
Date: Wed, 21 Jun 2000 14:44:23 -0400
"Trevor L. Jackson, III" wrote:
>
> Anton Stiglic wrote:
>
> > tomstd wrote:
> > >
> > > [EMAIL PROTECTED] (Mark Wooding) wrote:
> > > >S. T. L. <[EMAIL PROTECTED]> wrote:
> > > >> <<The optimists in the field believe that in 5 or 10 years
> > > >> it will be possible to build a quantum computer that can
> > > >> factor the number 4 as 2x2.>>
> > > >>
> > > >> I believe that 15's already been factored. Now for something
> > > big,
> > > >> like 77....
> > > >
> > > ><fx: hand in the air> Ooh! Ooh! I can do that one!
> > >
> > > Simple 77 = 23 * 9. I am glad I am doing goodly in math.
> > >
> > > Tom
> >
> > Well of course he was working mod 130, we all knew that!
>
> Ah yes, the invisible implicit modulus. Aren't they supposed to be prime?
He wasn't actually working in a cyclic group. ;)
Anton
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Generating Keys for 3DES
Date: Wed, 21 Jun 2000 14:50:10 -0400
You don't just want to do a single hash, you want key stretching.
See the article I referred to.
With a key stretching function, the output is indistinguishable
from the set of random elements of {0,1}^size_hash_ouput
Also, if the attacker wants to brute force the password, it will
take him a *long* time (with a simple single hash, it doesn't take much
time, hashes are super fast).
Anton
Joseph Ashwood wrote:
>
> The strength will be reduced to whatever the strength of the password is,
> however using SHA-1 is worthwhile, for several reasons:
> 1) If the attacker wants to attack the password there's an extra layer for
> them to go through, but still no more real entropy than in the password
> 2) If the attacker attacks the cipher you have 160-bits of apparent entropy
> (different from real entropy)
> and others, but these are the most important
> It just makes life more difficult for the attacker, which is exactly what is
> desirable.
> Joe
> > In a slightly related question, what if you want to do 3DES from
> > a password that happens to be less than 160 bits? Say the users
> > are too lazy to enter long passwords; could you still use SHA1 to
> > create a useful 160 bits from a 56 bit password?
------------------------------
Date: Wed, 21 Jun 2000 15:03:01 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Encryption on missing hard-drives
[EMAIL PROTECTED] wrote:
> Mack <[EMAIL PROTECTED]> wrote:
> > b) some spy now has the
> > codes to the PAL for nuclear
> > weapons. or whatever was on
> > the disks. since the information
> > was only secret I doubt it was
> > that important
>
> The missing disks were field manuals for NEST (Nuclear Emergancy
> Response Team). That is, they include schematics of most of the
> world's nuclear weapons and instructions for safetly opening the case,
> along with similar information.
>
> The reason it's only secret is partly because it needs to be accesible
> to NEST members, but also because the theory behind a nuclear device
> is much more readily available than during say The Manhattan
> Project. Given the wide proliferation of them, it's unclear how many
> improvements you could squeeze off the American ones. I mean, they
> probably have a much higher yield, and better guidance, but I wouldn't
> want a bomb made in India falling in my backyard either!
>
> Instructions for safe dissasembly are also less ominous than they
> sound, since you would need a bomb to open to make use of them. That
> implies either stealing a weapon, which is generally kept in
> facilities slightly more secure, or intercepting one during delivery,
> which is highly unlikely given the US delivers them by missile and
> bomb exclusively.
The U.S. has used alternative delivery mechanisms in the past, and may have
the capability to do so now. Also, we occasionally lose them. Remember the
big ones dropped off the coast of Spain?
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Standards for Internet Banking
Date: 21 Jun 2000 19:04:26 GMT
Standards for financial institutions are are http://www.x9.org. They are
available for purchase.
Don Johnson
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Blum-Williams integer????
Date: Wed, 21 Jun 2000 19:07:39 GMT
OTTO wrote:
> I have reads some paper about the cyptigraphy.....
> I do not understand "Blum-Williams integer" ~~~
> Somebody can help me~~~
Product of two distinct primes p and q, p congruent
to 3 mod 8, q congruent to 7 mod 8.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Ken Christensen" <[EMAIL PROTECTED]>
Subject: CRC-64 and 128 - Generator Polynomials?
Date: Wed, 21 Jun 2000 16:00:32 -0400
Are there "standard" generator polynomials for 64 and 128-bit CRC? I want
to study how CRC128 compares to MD5 in terms of 1) computation cost in s/w,
2) gate count in h/w, and 3) probability of collisions (duplicate hashes)
for hashing of Web URLs. Using remainder methods for computing CRC in s/w
seems to me would require less CPU cycles than MD5???
Thanks!
Ken Christensen
--
===============================================================
= Kenneth J. Christensen, Ph.D., P.E. (Assistant Professor) =
= Department of Computer Science and Engineering =
= University of South Florida =
= (813) 974-4761 =
= http://www.csee.usf.edu/~christen =
===============================================================
------------------------------
From: Stafford Tavares <[EMAIL PROTECTED]>
Subject: Papers Accepted for SAC 2000
Date: Wed, 21 Jun 2000 15:56:46 -0400
Workshop on Selected Areas in Cryptography
August 14-15, 2000
Universit of Waterloo
Waterloo, Ontario, Canada
Papers Accepted for SAC 2000
(For further information about SAC 2000, please see the website
at
http://www.cacr.math.uwaterloo.ca/conferences/2000/SAC2000/announcement2.html)
1. K. Aoki, T. Ichikawa, M. Kanda, M. Matsui, S. Moriai, J. Nakajima
and T. Tokita,
"Camellia: A 128-Bit Block Cipher Suitable for Multiple
Platforms".
2. C. Gunther, T. Lange and A. Stein,
"Speeding up the Arithmetic on Koblitz Curves of Genus Two".
3. A. Youssef,
"Cryptanalysis of the "Augmented Family of Cryptographic Parity
Circuits"
proposed at ISW '97".
4. V. Canda, T. van Trung, S. Magliveras and T. Horvath,
"Symmetric Block Ciphers Based on Group Bases".
5. J. Golic,
"Modes of Use of Stream Ciphers".
6. N. Park, J. Hwang and P. Lee,
"HAS-V: A New Hash Function with Variable Output Length".
7. K. Kurosawa, T. Iwata and V. Quang,
"Root Finding Interpolation Attack".
8. C. Blundo, A. De Bonis, B. Masucci and D. Stinson,
"Dynamic Multi-Threshold Metering Schemes".
9. J. Pliam,
"A Polynomial-Time Universal Security Amplifier in the Class
of Block Ciphers".
10. L. Simpson, E. Dawson, J. Golic and W. Millan,
"LILI Keystream Generator".
11. P. Nguyen and S. Vaudenay
"DFCv2".
12. H. Wu,
"On Complexity of Polynomial Basis Squaring in F2m".
13. G. Gong and A. Youssef,
"On Welch-Gong Transformation Sequence Generators".
14. M. Zhang, C. Carroll and A. Chan,
"Analysis of IS-95 CDMA Voice Privacy".
15. C. Adams and R. Zuccherato,
"A Global PMI for Electronic Content Distribution".
16. D. McGrew and S. Fluhrer,
"Attacks on Additive Encryption of Redundant Plaintext and
Implications on Internet Security".
17. K. Ohkuma, H. Muratani, F. Sano and S. Kawamura,
"The Block Cipher Hierocrypt".
18. Y. Zheng and X.-M. Zhang,
"Improving Upper Bound on Nonlinearity of High Order
Correlation
Immune Functions".
19. F. Bergadano, D. Cavagnino and B. Crispo,
"Chained Stream Authentication".
20. S. Vaudenay,
"Decorrelation over Infinite Domains: the Encrypted CBC-MAC
Case".
21. D. Huhnlein, M. Jacobson, Jr. and D. Weber,
"Towards Practical Non-interactive Public Key Cryptosystems
using
Non-maximal Imaginary Quadratic Orders".
22. H. Seki and T. Kaneko,
"Differential Cryptanalysis of Reduced Rounds of GOST".
23. M. Kanda,
"Practical Security Evaluation against Differential and Linear
Attacks for Feistel ciphers with SPN round function".
24. D. Huhnlein and S. Paulus,
"On the Implementation of Cryptosystems Based on Real Quadratic
Number Fields".
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Missing Info in the crypto-gram of MR BS
Date: 21 Jun 2000 20:17:20 GMT
I don't often go to the BS site about encryption
because maybe its his physics trainning. I have
a Master Degree in Electronic Engineering Control Theory
and we seldom see eye to eye.
Like many of his Crypt Grams this one starts very proper
and talks about Claude Shannon who in the 40's came up
with the concept called "unicity distance" He states that
English would require about 8.2 bytes of data for DES type of
cypher. Claude Shannon is the kind of genuis that Mr BS
is not. He goes on to state for Des only 2 cipher text blocks
need to be decoded. If the first block looks like English
and the second block also looks like English "you've found
the correct key". At this point he goes to state that
compression increases the "unity distance". It is at this
point that he does those wishing to understand the science
of encryption a disservice and the NSA would give him bonus
points. The fact is most "compression does not really add
to the unity distance".
What either Mr BS fails to understand or is misleading people
about. Is that most compression help the attacker and his
statement about compression increasing the unity distaance
and the statement about a random file haveing infinte unicity
distance is quite false for most compression schemes.
The main thing hidden from the user is for the compression
to actually increase the unity distance not only does the file
have to compress but the compression routines used must be
of the following form. for any file that is the result of
a "wrong key" that resulting file must be such that when it
is uncompressed to a test file. That file must compress back
exactly to the resulting file. This eliminates many canditate
files. It can eliminate so many files that the NSA does not
even need to know what kind of file you are compressing since
contrary to the statement that a random file has infinite unicity
they could in fact pretend they have zero knowledge about
the file. And only search for one by whatever means at there
disposal to find one that when uncompressed and compressed back
comes back to the test file. Since for most compression schemes
for files of most lengths there would only be one solution.
This to me means that the unicity distance is far form infinity
and that one should be very careful about what compression one
uses when encrypting data since there is lot that Mr BS chose
to leave out of his so called crypt gram.
check out http://members.xoom.com/ecil/compress.htm
at hss pointers to Tim's and Matt's site they seem
to have more of an understanding about what this kind
of compression is than anything you would find at the
BS site.
David Scott
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Encryption on missing hard-drives
Date: Wed, 21 Jun 2000 20:27:18 GMT
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> The U.S. has used alternative delivery mechanisms in the past, and may have
> the capability to do so now. Also, we occasionally lose them. Remember the
> big ones dropped off the coast of Spain?
Well, as far as I know the only two actually delivered (to a target,
not by train) were the two famous bombs. :) On the other hand, there's
a certain logic to the point that even if someone manages to steal one
it's better to have them open it safetly rather than unsafely. Even
without a detanation, the radioactive material escaping into the local
atmosphere or water table would be a real mess.
About the worst case I can imagine from the entire fiasco is that the
information allows someone to open a tamper-proof guidance or similar
high-tech system unreleated to the actual detonation mechanism.
On a more sci.crypt note, noone's answered my original question which
is if it's possible to encrypt a device such that it's impossible to
read the contents without leaving a trail. Something similar to a one
time password system, where a series of keys must be used or some
other clever algorithm. Just for fun, we'll allow a secure connection
to a trusted party.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Mike Andrews)
Subject: Re: Encryption on missing hard-drives
Date: Wed, 21 Jun 2000 20:33:59 GMT
Scripsit Douglas A. Gwyn <[EMAIL PROTECTED]>:
: [EMAIL PROTECTED] wrote:
:> The reason it's only secret is partly because it needs to be accesible
:> to NEST members, ...
: I know that agencies often do that sort of thing, but the official
: regulations require that classification (UNCLASSIFIED, CONFIDENTIAL,
: SECRET, TOP SECRET) be based only on the likely level of damage to
: national security should the information fall into the wrong hands.
Which is why the astronaut debriefing tape I heard after one of the
Gemini missions, in which the astronauts complained about having
apricots 3 meals in a row, was classified CONFIDENTIAL.
No, there was nothing else on the the tape which merited any sort
of classification. It was just the gripes about the apricots. The
other debriefing tapes I copied were all UNCLAS and not even FOUO.
OTOH, if these manuals contain schematics and disarming procedures
for non-US [thermo]nuclear weapons, it would make sense to label
them TS (and NOFORN and LIMDIS and all sorts of other things) just
so the non-US weapons-makers wouldn't be aware of the extent and
depth of our knowledge. Disclosure of the contents would let the
non-US weapons makers build booby-traps that could take advantage
of what we thought the disarm procedures should be -- and thereby
cause exceptionally grave damage to the national security of the US,
which used to be (and may still be) the criterion for TS.
When my father was in the Air Corps, he was EOD (and still has all
his fingers, too); his EOD manuals were SECRET for a good reason.
--
"The most interestign thing about king Charles I is that he was 5' 6" at
the beginning of his reign and 4' 8" at the end of it, and all because
of..."
-- from [alt.fan.pratchett] Re: [I] Exam questions
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Date: Wed, 21 Jun 2000 15:20:53 -0500
Mok-Kong Shen wrote:
>
> Mark Wooding wrote:
>
> > [snip]
> >
> > OK. Let p, q be prime numbers, p = q = 3 (mod 4), and let n = p q.
> > Choose an integer x, 0 < x < n. Then y = x^2 (mod n) is a quadratic
> > residue, mod n.
> >
> > I claim (a) that y has four square roots, mod n, and (b) that exactly
> > one of these square roots is a quadratic residue.
>
> Counter-example: p=3, q=7, n=21. 7 is quadratic residue, since
> 7^2 = 49 = 7 mod n. However 7 has only 2 square roots: 7 and 14.
> (Bryan Olson's proof must also have a bug somewhere.)
>
> M. K. Shen
His mistake lies in assuming that GCD(x,p)=1, i.e. that x mod p is
distinct from -x mod p. Add the assumption that x is relatively prime
to p and q and he's safe. Often this is done by assuming x<p<q which is
not really such a major assumption.
Doug
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Missing Info in the crypto-gram of MR BS
Date: Wed, 21 Jun 2000 15:58:36 -0500
"SCOTT19U.ZIP_GUY" wrote:
> I don't often go to the BS site about encryption
> because maybe its his physics trainning. I have
> a Master Degree in Electronic Engineering Control Theory
> and we seldom see eye to eye.
>
> Like many of his Crypt Grams this one starts very proper
> and talks about Claude Shannon who in the 40's came up
> with the concept called "unicity distance" He states that
> English would require about 8.2 bytes of data for DES type of
> cypher. Claude Shannon is the kind of genuis that Mr BS
> is not. He goes on to state for Des only 2 cipher text blocks
> need to be decoded. If the first block looks like English
> and the second block also looks like English "you've found
> the correct key". At this point he goes to state that
> compression increases the "unity distance". It is at this
> point that he does those wishing to understand the science
> of encryption a disservice and the NSA would give him bonus
> points. The fact is most "compression does not really add
> to the unity distance".
Headerless compression will add to the unicity distance assuming that
the file is compressible. The reasoning being that since more of the
space of possible plaintexts being inputed is used, the unicity distance
must therefore increase.
>
> What either Mr BS fails to understand or is misleading people
> about. Is that most compression help the attacker and his
> statement about compression increasing the unity distaance
> and the statement about a random file haveing infinte unicity
> distance is quite false for most compression schemes.
A file of random data will have an infintie unicity distance no matter
what compression scheme is used. However, I will agree that compression
will NOT always increase unicity distance, though it should at worst
leave the distance unchanged.
>
> The main thing hidden from the user is for the compression
> to actually increase the unity distance not only does the file
> have to compress but the compression routines used must be
> of the following form. for any file that is the result of
> a "wrong key" that resulting file must be such that when it
> is uncompressed to a test file. That file must compress back
> exactly to the resulting file. This eliminates many canditate
> files.
I am agreed that this is sub optimal. However, this is not necessarialy
worthless, as if even one possible is added, the unicity distance is
increased.
> It can eliminate so many files that the NSA does not
> even need to know what kind of file you are compressing since
> contrary to the statement that a random file has infinite unicity
> they could in fact pretend they have zero knowledge about
> the file. And only search for one by whatever means at there
> disposal to find one that when uncompressed and compressed back
> comes back to the test file. Since for most compression schemes
> for files of most lengths there would only be one solution.
Agreed in a general sense. However, I think you are misunderstanding his
statement in re: a "random file" his statement is in refrence to a file
of totally random data, I believe you are reading it as a "file chosen
at random"
>
> This to me means that the unicity distance is far form infinity
> and that one should be very careful about what compression one
> uses when encrypting data since there is lot that Mr BS chose
> to leave out of his so called crypt gram.
>
> check out http://members.xoom.com/ecil/compress.htm
> at hss pointers to Tim's and Matt's site they seem
> to have more of an understanding about what this kind
> of compression is than anything you would find at the
> BS site.
>
> David Scott
> .
I do agree that a so called 1-1 compression method is to be desired so
far as adding to the unicity distance. However, even such a method will
not result in an infinite unicity distance, as the output will still
have predictable character given that the input is predictable. ( I.e.
you uncompress your decryption and it should also have characteristics
similar to that of the original plaintext space.) I do not feel that he
left an extensive amout of material out, merely that he was stating
generalities.
------------------------------
Subject: Quick Question on Primitive Elements GF(p)
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Wed, 21 Jun 2000 11:29:04 -0700
Is the definition of a number that is a primitve element GF(p),
if you can mutliply it by itself over and over, and get every
value 0.....p-1?
Or is this a side effect of some other definition?
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
** 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
******************************
