Cryptography-Digest Digest #724, Volume #10 Sat, 11 Dec 99 16:13:01 EST
Contents:
Insecure PRNG? ("Gary")
Insecure PRNG? ("Gary")
Re: some questions about DES (Tom St Denis)
Re: Linear Congruential Generators (Mok-Kong Shen)
Re: some questions about DES (Troed)
Re: some questions about DES ([EMAIL PROTECTED])
Re: Linear Congruential Generators (David A Molnar)
New Algorithm (Jeroen van de Erve)
Re: Scott's Screaming Security Method (Loney Ramik)
Re: Insecure PRNG? (Mok-Kong Shen)
Re: New RNG Technique (Loney Ramik)
Re: Attacks on a PKI (David A Molnar)
Re: New Algorithm (Mok-Kong Shen)
Brute Force Time (Maximum v Probable) (UBCHI2)
Re: New Algorithm (Loney Ramik)
Re: some questions about DES (Gunnar Andersson)
Re: If you're in Australia, the government has the ability to modify (Darren New)
Re: Linear Congruential Generators (Mok-Kong Shen)
Re: some questions about DES (Jerry Coffin)
Re: Questions about message digest functions (Tim Tyler)
----------------------------------------------------------------------------
From: "Gary" <[EMAIL PROTECTED]>
Subject: Insecure PRNG?
Date: Sat, 11 Dec 1999 17:27:00 -0000
Insecure PRNG?
Linear congruential Pseudo-Random Number Generators (PRNG) of the form
Xn+1=AXn+B are always stated to be insecure as the basis of a cipher
bit-stream.
If only the top bit is used on a PRNG of this form how do I find the
constants X0,A and B., without brute force?
IE Given a large cipher bit-stream produced by the following C function
long NextBit(void)
{
static long X=X0;
X=(X*A)+B;
return (X>>31);
}
How do I determine constants X0,A,B collectively forming a key to the cipher
stream?
(The 3 constants are randomly generated but B is odd and A=1(mod 4))
More over, if two PRNGs of this form were used where the top 5 bits of the
first's output are used to select the single cipher-stream bit in the
second's output, how do I go about solving this?
IE Given a large cipher bit-stream produced by the following C function
long NextBit(void)
{
static long X=X0,Y=Y0;
X=(X*A)+B;
Y=(X*C)+D;
return ((X>>((Y>>27)&31))&1);
}
How do I determine constants X0,Y0,A,B,C,D collectively forming a key to the
cipher stream?
(The 6 constants are randomly generated but B,D odd and A,C=1(mod 4))
G.
------------------------------
From: "Gary" <[EMAIL PROTECTED]>
Subject: Insecure PRNG?
Date: Sat, 11 Dec 1999 17:29:09 -0000
Insecure PRNG?
Linear congruential Pseudo-Random Number Generators (PRNG) of the form
Xn+1=AXn+B are always stated to be insecure as the basis of a cipher
bit-stream.
If only the top bit is used on a PRNG of this form how do I find the
constants X0,A and B., without brute force?
IE Given a large cipher bit-stream produced by the following C function
long NextBit(void)
{
static long X=X0;
X=(X*A)+B;
return (X>>31);
}
How do I determine constants X0,A,B collectively forming a key to the cipher
stream?
(The 3 constants are randomly generated but B is odd and A=1(mod 4))
More over, if two PRNGs of this form were used where the top 5 bits of the
first's output are used to select the single cipher-stream bit in the
second's output, how do I go about solving this?
IE Given a large cipher bit-stream produced by the following C function
long NextBit(void)
{
static long X=X0,Y=Y0;
X=(X*A)+B;
Y=(Y*C)+D;
return ((X>>((Y>>27)&31))&1);
}
How do I determine constants X0,Y0,A,B,C,D collectively forming a key to the
cipher stream?
(The 6 constants are randomly generated but B,D odd and A,C=1(mod 4))
G.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: some questions about DES
Date: Sat, 11 Dec 1999 18:11:05 GMT
In article <82tt20$q4u$[EMAIL PROTECTED]>,
"Buchinger Reinhold" <[EMAIL PROTECTED]> wrote:
> Hi !
>
> I write a paper about DES for my school - leaving exam and I need some
> further informations.
>
> Where was and is DES used ?
> Has DES been verified in 1998 ?
> If not what's its succession ?
> How fast and with which computer (price) can DES been broken
nowadays ?
>
> If you have some references (websites, ...) for your knowledge please
let me
> know !
> I am VERY grateful for you help !
DES in it's original form is no longer used. It was originally used
primarly in hardware, but has been adapted for password hashing in
unix. 3DES is still in use today, primarly in software but some
hardware for it is out there.
It can be cracked with 120000 spare computers over the inet in about 20
hours. [well DES anyways].
It was originally broken with differential cryptanaylsis using 2^51
pairs. Then linear analysis in 2^47 [or something like that, I have a
paper by Biham on the Differential Cryptanalysis if you want].
That's all I know off hand.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Linear Congruential Generators
Date: Sat, 11 Dec 1999 19:40:31 +0100
Gary schrieb:
>
> Insecure PRNG?
>
> Linear congruential Pseudo-Random Number Generators (PRNG) of the form
> Xn+1=AXn+B are always stated to be insecure as the basis of a cipher
> bit-stream.
>
> If only the top bit is used on a PRNG of this form how do I find the
> constants X0,A and B.
I surmise that it might be better to use the parity bits of the output
of PRNGs. From experiments I found that parity bits from LCPRNGs
have fairly good statistical properties. I am not aware of methods
of inference on parity bits. But perhaps experts would like to furnish
such informations.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Troed)
Subject: Re: some questions about DES
Reply-To: [EMAIL PROTECTED]
Date: Sat, 11 Dec 1999 18:51:56 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>DES in it's original form is no longer used. It was originally used
(Except in all ViaSats Eurocrypt smartcards - both for encrypting the
master key updates and the user key updates. DES is also used to
encrypt the actual scanline positions and for making hashes)
___/
_/
Nazister, rasister och andra dårar - ger bara sig själva kalla kårar
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: some questions about DES
Date: 11 Dec 1999 19:02:26 GMT
Reply-To: [EMAIL PROTECTED]
In <82u43n$v90$[EMAIL PROTECTED]>, Tom St Denis <[EMAIL PROTECTED]> writes:
>In article <82tt20$q4u$[EMAIL PROTECTED]>,
> "Buchinger Reinhold" <[EMAIL PROTECTED]> wrote:
>> Hi !
>>
>> I write a paper about DES for my school - leaving exam and I need some
>> further informations.
>>
>> Where was and is DES used ?
>> Has DES been verified in 1998 ?
>> If not what's its succession ?
>> How fast and with which computer (price) can DES been broken
>nowadays ?
snip
>
>DES in it's original form is no longer used. It was originally used
>primarly in hardware, but has been adapted for password hashing in
>unix. 3DES is still in use today, primarly in software but some
>hardware for it is out there.
>
>It can be cracked with 120000 spare computers over the inet in about 20
>hours. [well DES anyways].
>
>It was originally broken with differential cryptanaylsis using 2^51
>pairs. Then linear analysis in 2^47 [or something like that, I have a
>paper by Biham on the Differential Cryptanalysis if you want].
>
>
>That's all I know off hand.
>
>Tom
>
DES (56) bit is used today to encrypt the PIN for ATM transactions
throught the US. The largest single user is the US dept of Agriculture
for the new food stamp program (EBT). Approx 3/4 million terminals
use DES to encrypt th user PIN.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Linear Congruential Generators
Date: 11 Dec 1999 18:58:04 GMT
Gary <[EMAIL PROTECTED]> wrote:
> Linear congruential Pseudo-Random Number Generators (PRNG) of the form
> Xn+1=AXn+B are always stated to be insecure as the basis of a cipher
> bit-stream.
> If only the top bit is used on a PRNG of this form how do I find the
> constants X0,A and B.
Answering that explicitly seems to take a fair amount of work...I'll
drop the references now and see if I get time to put something together
later. My apologies for being vague. :-(
There is a paper which explains how to go about recovering the
parameters of an LCG, even when only one bit of the output is known :
[FH+] A.M. Frieze, J. Hastad, R. Kannan, J.C. Lagarias,
A. Shamir. Reconstructing truncated integer variables satisfying linear
congruences. SIAM J. Comput. 17(2):262-280, Apr. 1988
Unfortunately, this paper isn't very readable. You may find some help
with the terms by looking at this "Lattices and Cryptography" course at
UCSD :
http://www-cse.ucsd.edu/~daniele/cse291fa99.html
(notice that Problem Set 1 has a truncated LCG on it)
Terry Ritter also posted a bibliography of papers on cracking LCGs to
sci.crypt a few months ago. That should still be in the news archives.
> More over, if two PRNGs of this form were used where the top 5 bits of the
> first's output are used to select the single cipher-stream bit in the
> second's output, how do I go about solving this?
I don't know off the top of my head, but it seems to me that you
might be able to get an equation relating the output to the top 5 bits
of your first generator. Maybe this can be leveraged?
-David Molnar
------------------------------
From: Jeroen van de Erve <[EMAIL PROTECTED]>
Subject: New Algorithm
Date: Sat, 11 Dec 1999 19:02:35 GMT
I would like to have attention about a new algorithm. Two Israeli
mathematicians have created a new encryption algorithm called Wolf_Cub.
Because this algorithm is very new, it hasn't yet been tested by one or
more cryptographers. Therefore I would like to ask if someone is
interested to "look" to the algorithm and give his/her comments.
One of the features of Wolf_Cub is support of unlimited length of
password and full impossibility to crack the encrypted file (of course
except the full consideration of all passwords).
If you're interested, please mail me at: [EMAIL PROTECTED]
(remove the nospam.). If you use PGP, please include your PGP Public
Key-ID.
Kind regards,
Jeroen van de Erve
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Loney Ramik)
Crossposted-To: comp.compression,alt.security
Subject: Re: Scott's Screaming Security Method
Date: Sat, 11 Dec 1999 19:20:21 GMT
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
>Any thoughts on this by my nonadmirers.
I'm a little puzzled by the name you chose. How will screaming help, Scott?
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Insecure PRNG?
Date: Sat, 11 Dec 1999 20:28:09 +0100
Gary wrote:
>
> Insecure PRNG?
>
> Linear congruential Pseudo-Random Number Generators (PRNG) of the form
> Xn+1=AXn+B are always stated to be insecure as the basis of a cipher
> bit-stream.
>
> If only the top bit is used on a PRNG of this form how do I find the
> constants X0,A and B., without brute force?
.......
> How do I determine constants X0,A,B collectively forming a key to the cipher
> stream?
> (The 3 constants are randomly generated but B is odd and A=1(mod 4))
>
> More over, if two PRNGs of this form were used where the top 5 bits of the
> first's output are used to select the single cipher-stream bit in the
> second's output, how do I go about solving this?
One can also add wordwise (e.g. 32 bits) the outputs from two or
more LCPRNGs. How to do analysis of that appears also to be
unknown. In a follow-up in another thread I mentioned the use of
parity bits. A method I used is to employ a number of generators
and let each generator produce on activation two numbers, one to
supply the outside world and the other to determine the successor
generator to be activated next.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Loney Ramik)
Subject: Re: New RNG Technique
Date: Sat, 11 Dec 1999 19:30:08 GMT
[EMAIL PROTECTED] (Steve Harris) wrote:
>I have developed a technique that converts the output of any RNG into a
>cryptographically secure bit stream good enough to pass all statistical tests
>for randomness, including DIEHARD.
I get the impression that you specifically designed your program to pass
those tests. If you did that, then none of those tests are useful in
evaluating your program. It's sort of like shooting at a blank sheet of
paper and then drawing targets around the places where your bullets hit.
--
"Loney Ramik" is actually [EMAIL PROTECTED] (7893 264015).
01234 56789 <- Use this key to decode my email address and name.
Play Five by Five Poker at http://www.5X5poker.com.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Attacks on a PKI
Date: 11 Dec 1999 19:07:15 GMT
DJohn37050 <[EMAIL PROTECTED]> wrote:
> I am part of a panel at RSA 2000 that is talking about public key validation
> and non-repudiation. A bogus key can be a problem in many various ways.
> Don Johnson
Out of curiosity, do you know of anyone discussing key validation for
PKCs other than RSA? I know that validation is supposed to be
immensely easier for Elgamal and elliptic curve, since the key is
simply a random number. Are there other systems which have come up?
Thanks much,
-David Molnar
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: New Algorithm
Date: Sat, 11 Dec 1999 20:34:25 +0100
Jeroen van de Erve wrote:
>
> If you're interested, please mail me at: [EMAIL PROTECTED]
> (remove the nospam.). If you use PGP, please include your PGP Public
> Key-ID.
Could you post a sketch of the algorithm or give a reference to
the original work instead of having individuals discuss with you on a
one-to-one basis?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (UBCHI2)
Subject: Brute Force Time (Maximum v Probable)
Date: 11 Dec 1999 19:35:59 GMT
1) You have a 50% chance of finding the key after only running only half the
possible keys. Basically, there is a 1 in 2 chance of the attack taking only
half the time allocated given the total possible number of keys.
2) You only have to search for keys equal to the keylength of the target. For
example, you only have to search for a key equal to 128, 256, 512, 1024. I
estimate that less than 1 in 100 people use a key of an "off" size. You don't
have to search for all keys smaller than 128. This cuts the number of keys
down by perhaps 50%.
In other words, .5*.5 is only 25%. This corresponds to the time needed to
attack a key with brute force versus the time allocated given the total number
of possible keys.
The industry should shift from quoting maximum time to crack a key to quoting
probable time to crack a key.
------------------------------
From: [EMAIL PROTECTED] (Loney Ramik)
Subject: Re: New Algorithm
Date: Sat, 11 Dec 1999 19:40:33 GMT
Jeroen van de Erve <[EMAIL PROTECTED]> wrote:
>One of the features of Wolf_Cub is...
>... full impossibility to crack the encrypted file (of course
>except the full consideration of all passwords).
That absurd claim pretty much guarantees that cryptographers won't bother
to look at it seriously. I suggest that you advise the authors that if
they're really interested in cryptography, they should study the field
first.
--
"Loney Ramik" is actually [EMAIL PROTECTED] (7893 264015).
01234 56789 <- Use this key to decode my email address and name.
Play Five by Five Poker at http://www.5X5poker.com.
------------------------------
From: Gunnar Andersson <[EMAIL PROTECTED]>
Subject: Re: some questions about DES
Date: Sat, 11 Dec 1999 20:32:31 +0100
On Thu, 9 Dec 1999, Buchinger Reinhold wrote:
> How fast and with which computer (price) can DES been broken nowadays ?
Electronic Frontier Foundation built a machine costing < $250K to
build which tries the entire key space (2^56 keys) in a couple of
days, for details see
http://www.eff.org/pub/Privacy/Crypto_misc/DESCracker/
/ Gunnar
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: If you're in Australia, the government has the ability to modify
Date: Sat, 11 Dec 1999 19:45:29 GMT
Trevor Jackson, III wrote:
> I suppose if they are aiming Really Bad Software at the masses
> of amateur developers quality doesn't matter -- most of their customers can't tell
> the difference.
I think you're confused as to who Microsoft's customers are. Not that *this*
is on topic either. :-)
--
Darren New / Senior Software Architect / Dai Ye
San Diego, CA, USA (PST). Cryptokeys on demand.
"Perl - The BASIC of the 90's"
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Linear Congruential Generators
Date: Sat, 11 Dec 1999 20:58:56 +0100
David A Molnar wrote:
> > More over, if two PRNGs of this form were used where the top 5 bits of the
> > first's output are used to select the single cipher-stream bit in the
> > second's output, how do I go about solving this?
>
> I don't know off the top of my head, but it seems to me that you
> might be able to get an equation relating the output to the top 5 bits
> of your first generator. Maybe this can be leveraged?
I suppose it is always essential to distinguish between theoretical
and practical solvability (with the available resources). Just because
something is in principle clearly solvable doesn't mean it is useless
in crypto applications. The apparently common avoidance of matters
that have anything to do with linearity isn't always justified in
my humble opinion.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: some questions about DES
Date: Sat, 11 Dec 1999 13:07:22 -0700
In article <82tt20$q4u$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> Hi !
>
> I write a paper about DES for my school - leaving exam and I need some
> further informations.
>
> Where was and is DES used ?
Where is air used? All over everywhere in all sorts of situations.
> Has DES been verified in 1998 ?
> If not what's its succession ?
NIST has released a draft of FIPS 46-3, which specifies the use of
triple-DES rather than single DES. The last time I looked (admittedly
a few months ago) FIPS 46-2 was still the legal standard though.
> How fast and with which computer (price) can DES been broken nowadays ?
AFAIK, there's only one publicly known DES breaking machine. It will
break DES in about a day and cost about $250,000US to build. It's a
few years old and that included design costs, so another could be
built for substantially less now but if anybody has done so, I'm not
aware of it.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Questions about message digest functions
Date: Sat, 11 Dec 1999 20:03:11 GMT
In sci.crypt, lordcow77 wrote:
> <[EMAIL PROTECTED]> wrote:
> > Hash functions may be made from block cyphers.
> > Block cyphers are reversible. Consequently,
> > a message hash of a message with the hash
> > size, the block size and the message size all
> > equal will be a bijection. [...]
>
> Idiot. [...]
*Rarely* a good start to a usenet post in a
technical forum.
> The construction that transforms a block
> cipher cryptographic primative into a hash
> function should destroy the bijectiveness of
> the block cipher.
No. You are mistaken.
Consider a common technique of transforming a
block cypher into a hash:
Apply the block cypher in a chaining mode to
the message. Take the last block of cyphertext as
the hash.
When applied to a single block, this *retains* the
bijective nature of the block cypher. This
is, in fact, a useful thing for it to do.
> A hash function should be indistinguishble from
> a random function, not random permutation.
No. You are mistaken.
No hash function should *ever* be
indistinguashable from a random function.
If it /does/ have the characteristics of a random
function, this means hash collisions are more likely
to occur - and consequently easier to find - than
they could be.
The whole point of hashing is to make finding hash
collisions as difficult as possible. A function
which acts like a random function demonstrably
fails to do this.
> A random function should have images
> that cannot be reached from preimages of the
> same length as the image.
True - but irrelevant to the subject of hashing.
Please forgive me - but I'm curious as to how
you can be so bold as to call me an idiot - and
then go on to spout nonsense in such an
authoratative manner.
Can you remember how you arrived at the mistaken
idea that hashes should simulate random functions?
Has anyone else apart from you ever claimed this?
--
__________
|im |yler
Destroy Microsoft.
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
******************************
