Cryptography-Digest Digest #443, Volume #13 Mon, 8 Jan 01 23:13:01 EST
Contents:
Re: Fastest way to factor primes? (Simon Johnson)
Re: secure RNG ("Joseph Ashwood")
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post) ("Paul Pires")
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: NIST hmac fips (DJohn37050)
Re: xor'd text file (Forrest Johnson)
Re: NSA and Linux Security (Eric Lee Green)
Re: secure RNG (Eric Lee Green)
Re: Linear analysis (Benjamin Goldberg)
Re: secure RNG (graywane)
Re: Comparison of ECDLP vs. DLP (Roger Schlafly)
----------------------------------------------------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Fastest way to factor primes?
Date: Tue, 09 Jan 2001 00:01:42 GMT
In article <93djd1$h78$[EMAIL PROTECTED]>,
Bryan Olson <[EMAIL PROTECTED]> wrote:
> Simon Johnson wrote:
> [...]
> > Well if it isn't, i'm sorry for providing disinformation. But in
> > Applied Cryptography the NFS time estimate is given by the following
> > function, is this not an expondential function:
> >
> > e^(1.923+0(1))(ln(n))^(1/3)(ln(ln(n)))^(2/3)
>
> Well, no it isn't.
>
> > And if so, why not?
>
> There are a few issues arguably worth noting:
>
> (1.923+0(1)) is nonsense. That should be a lower-case
> "o", not a capital "O" as in Applied Cryptography, or a
> zero as above.
>
> Under normal precedence rules, you need another pair of
> parenthesis, around the entire exponent (everything after
> "e^").
>
> The given function is sub-linear. Note that "n" stands
> for the number to be factored, not the size of bits.
>
> As a function of the bit-size of n, the expected running
> time of the GNFS is super-polynomial, but sub-exponential.
>
> --Bryan
>
> Sent via Deja.com
> http://www.deja.com/
>
Noted!
Thanks,
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: secure RNG
Date: Mon, 8 Jan 2001 16:12:22 -0800
I'm sorry but finding what you seem to be looking for can't happen. Please
feel free to correct me if I'm wrong, but you are looking for a Pseudo
Random Number Generator that given a small password (or other finitely sized
key) and create an infinitely long stream of numbers that are secure. I'm
sorry but such a thing can't exist. We do however have things that can for
many purposes be treated similarly, or have different behavior that gives
close to the results you desire. A fairly good best of breed list of these
are:
Blum, Blum, Shub (http://www.io.com/~ritter/NEWS2/TESTSBBS.HTM about half
way down the page)
RC4 (aka ARCFOUR) (http://burtleburtle.net/bob/rand/isaac.html#RC4)
ISAAC (http://burtleburtle.net/bob/rand/isaac.html#ISAAC)
Yarrow (http://www.counterpane.com/yarrow)
They all take different approachs. Blum, Blum, Shub is provably secure under
certain assumptions, but horribly slow. RC4 is very fast but has a bias,
ISAAC is not quite as fast but IIRC has a lower bias. Yarrow is a different
class of design, it makes use of entropy gathering on the local machine and
does not make use of a finitely sized key. On the same page as ISAAC and RC4
you'll find code for others as well.
Joe
"Dobs" <[EMAIL PROTECTED]> wrote in message news:93da5a$5j1$[EMAIL PROTECTED]...
> I am looking for good random number generator which can be used in
> cryptography, ( for example in key generating) . If anybody knows where I
> can find such a secure generators implemented in C ( not in Visual C :),
> Could You please write me back or send it to me. I need 3,4 or 5 such a
> generators to compare. I would be greatful for help:))))
> Best regards
>
>
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post)
Date: Mon, 8 Jan 2001 16:13:41 -0800
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Paul Pires wrote:
<snip>
> > *if you can make a stream cipher that breaks the locational
> > relationship between ciphertext, state and plaintext. AND
>
> I'm confused, what do you mean by this item?
Assume encryption is key XOR plaintext = ciphertext.
Well, if you had a stream cipher that outputted it's ciphertext units
(bits, bytes or whatnot) in a different order than that of the plaintext
and let's say that this mapping changed constantly and unpredictably
within a subset of the message, kinda like a block, say 512 bits.
This mapped ciphertext could now be XOR'd back with the plaintext
to produce !key (Not key). This !key could be added back into the
state of the cipher for feed back and three things now happen.
1, the attacker doesn't know which bit to flip to effect what bit and
2, flipping a bit causes the internal state to change so that subsequent
ciphertext decrypts to garbage.
3, You wouldn't want to fold a conventional key stream back into
itself by XOR as it would cancel out and zero the internal state. By
the same token, giving the attacker a big chunk of the internal state
(You have to assume they have known plaintext & ciphertext & can XOR
them together) This would be dumb as it is the running key.
Ciphertext XOR plaintext is not the internal state
unless one knows the mapping.
Of course, to decrypt, you would also have to un-map.
In a stream cipher like this the ending state is a function of the starting
keyed state, the ciphertext and the plaintext. A lossy reduction of the
ending state (like a hash) would serve as a signature of that session.
flipping a bit will result in a different ciphertext, plaintext, internal state
and therefore, a different signature.
The nice thing is that you don't have to hash the whole message, just
the last internal state.
> > *if you can make a stream cipher that automagically authenticates. AND
>
> For a cipher, stream or otherwise, to authenticate, you need one of two
> things: it either must output garbage if an opponent changes some bits
> of the ciphertext, or it must have appended to it some sort of secure
> error checking code.
To be fair, I think you have to say that a secure error checking code MUST
be used. Files are rarely read by people anymore and to effectively recognize
"garbage" there has to be some kind of crc or verification. The "signature"
above fills that role.
> For a stream cipher, the second can be done by appending a CRC or secure
> hash. To do the first with a stream cipher, I would guess that if XOR
> of keystream and plaintext was replaced with dynamic substitution, this
> might work (maybe). See Terry Ritter's pages on that, and on his Cloak2
> stream cipher.
>
> For any block cipher, flipped ciphertext bits will result in that block
> being garbage. For the error to propogate to the entire file, one
> should use some sort of chaining, perhaps PCBC.
>
> > *if you can do these things without loosing the speed and simplicity
> > advantages......
> >
> > Then, it might just be interesting.
> >
> > I have been playing around with a few ideas that lead me to believe
> > that the first two ideals and "Stream" are not incompatible. The third
> > is a little tougher :-)
>
> Well, the second is surely possible, and without adding significant time
> or complexity, but I don't know what you mean by the first.
Hope this helps,
Paul
>
> --
> Power interrupts. Uninterruptable power interrupts absolutely.
> [Stolen from Vincent Seifert's web page]
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 09 Jan 2001 01:23:02 GMT
Subject: Re: Comparison of ECDLP vs. DLP
Any security proof relies on assumptions. I think the proof is random oracle,
which some do not accept.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 09 Jan 2001 01:23:52 GMT
Subject: Re: NIST hmac fips
Yes, min of 4, but this is restricted to special cases.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Forrest Johnson)
Subject: Re: xor'd text file
Date: 8 Jan 2001 22:43:21 GMT
[EMAIL PROTECTED] (Joshua Cryer) wrote in
<SmO56.16021$[EMAIL PROTECTED]>:
>> I dont quite understand what you mean by 'seed'. The number 65535 is
>16bits
>> in binary. Do you mean the number which is <= 65535 has been XOR'd
>> with
>every
>> 16 bits in the text file? If that was the case then frequency analysis
>would
>> still work pretty well on the file. Look at how many times each byte
>occurs
>> in the text file. The highest frequencied items will most likely be
>plaintext
>> space or E. From there you can figure out what number would transfer
>> the ciphertext letter into space or E. Apply this to the whole file
>> and see
>what
>> happens.
>
>What I mean is this. The file is XOR'd to a pseudo-random number
>generator which is limited to 65535 possible seeds (yeah, 16 bits). I
>actually know many words, and even complete sentences that were used in
>the original text file. I just don't know how I could begin to reverse
>engineer since I know for certian that it was XOR'd at least twice
>(maybe more) with two different seeds. Someone told me that this is very
>crackable. Well. How?
>
>
You mentioned in your original post that the enciphered file is very large.
Is it larger than 65535 bits? If so, you should be able to take advantage
of the fact that a PRNG has a period that is very commonly equal to the
size of the seed space. Thus, the cipher stream from the PRNG will start
repeating after 65535 bits.
Even if the text was enciphered several times, using the same PRNG with
different keys would still produce this cyclic pattern. The XOR function
is commutative, so it doesn't matter what the order of application is -- A
XOR B XOR C is equal to A XOR C XOR B. In addition, the operation of A XOR
B XOR C is equivalent to A XOR Z where Z is equal to B XOR C. In other
words, repeatedly XORing the plaintext file with a succession of values is
the equivalent of XORing it with some other single value.
Given this property and the cyclic nature of the PRNG, an XOR of the first
enciphered bit with the 65536th bit will produce a a result equal to the
two plaintext bits (1 and 65536) XORed together (providing the cycle is
65535). If you know the plaintext value of bit 1, you could then extract
the plaintext value of bit 65536.
You said that you knew some plaintext already. If you know the position of
this plaintext in the file, you could test what I've suggested:
1) Take a string of enciphered text equal to the length of the known
plaintext from the same position as the known plaintext.
2) XOR this string with another string equal in length and positioned one
cycle away. The result should be two plaintext strings XORed together.
3) Finally, take your known plaintext and XOR it with the result of step 2.
This should produce the second plaintext string. If you get gibberish, it
means that the cycle length is wrong, the known plaintext is wrong, or the
position of the known plaintext is wrong.
You can also recover the portion of the cipher stream used for that string
by XORing the enciphered text with the plaintext. If your file is several
cycles long, you can then apply this recovered cipher stream to the proper
positions in each cycle to extract the plaintext.
If you don't know the position of the known plaintext, try a sliding window
approach (using a technique similar to that described above) on enciphered
strings that are a cycle apart and check the results for non-gibberish.
If you don't know either the cycle length or the position of the known
plaintext, you can still attack the enciphered text but it is going to be
very tedious. It involves sliding the known plaintext throughout the file
until you discover a cycle length that yields non-gibberish.
Once you recover some plaintext from the enciphered file, make some guesses
as to what other plaintext might be and apply the 3-step approach to check
your guesses. (If you get gibberish at a cycle away, your guess was
wrong.)
Of course, this attack depends on the file being longer than one cycle of
the PRNG. If it's shorter than that, this type of attack will not work.
------------------------------
From: [EMAIL PROTECTED] (Eric Lee Green)
Subject: Re: NSA and Linux Security
Reply-To: [EMAIL PROTECTED]
Date: Tue, 09 Jan 2001 03:10:33 GMT
On Mon, 8 Jan 2001 16:16:49 GMT, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>Simon Johnson wrote:
>> ... I remember once reading that the NSA broke the
>> encryption of between an candian exporter of grain and some EU
>> distrubuter. The NSA then promptly sold this information to an American
>> supplier and the American comapny successfully undercut the deal.
>
>If you have evidence of this (highly illegal) event,
>please send it to me and I'll see that an investigation
>is launched. Frankly I doubt that it occurred, but if
>it did the individual responsible should be prosecuted.
Huh? If the NSA sold the information (as vs. gave it to the American
supplier) it was illegal, but I thought that part of the NSA's new
mission was interception of "signals of economic import"? As in, if
they intercept some data overseas that is of benefit to an American
business, they are free to turn over that data to that business if it
is felt to be "in the national interest"?
As far as I know, there are no laws restricting what data the NSA can
intercept (other than that it must be overseas and not between U.S.
citizens, which falls under the FBI's jurisdiction). I don't know of
any law prohibiting the NSA from disclosing such data to American
companies if it is felt to be "in the national interest". Do you have
a reference to any such laws or regulations?
--
Eric Lee Green Linux Subversives
[EMAIL PROTECTED] http://www.badtux.org
------------------------------
From: [EMAIL PROTECTED] (Eric Lee Green)
Subject: Re: secure RNG
Reply-To: [EMAIL PROTECTED]
Date: Tue, 09 Jan 2001 03:18:07 GMT
On Mon, 8 Jan 2001 22:03:46 +0100, Dobs <[EMAIL PROTECTED]> wrote:
>I am looking for good random number generator which can be used in
>cryptography, ( for example in key generating) . If anybody knows where I
>can find such a secure generators implemented in C ( not in Visual C :),
>Could You please write me back or send it to me. I need 3,4 or 5 such a
>generators to compare. I would be greatful for help:))))
/dev/random on Linux and (Free|Open)BSD is an interesting random number
generator. Yarrow on Windows ( http://www.counterpane.com/yarrow if I
remember correctly) is one for Windows.
If you are looking for pseudo-random-number generators, the net can be
cast a bit wider. I wrote one for Unix called "Ocotillo", which is at
least better than rand(3) (sigh) though nowhere near as good as one
that can hitch into systems internals like /dev/random or
Yarrow. /dev/urandom on Linux and *BSD turns into md5 in counter mode
if you attempt a flood attack against it, but gets re-seeded with a
random value whenever /dev/random reports that it has adequate
entropy.
OpenSSL ( http://www.openssl.org ) and GNU Privacy Guard (
http://www.gnupg.org ) both claim to have good PRNG's.
I think that's enough for now. You probably also want to read Bruce
Schneir's paper on the design of Yarrow, and David Wagner's paper on
how he broke the Netscape SSL by taking advantage of a defective PRNG.
There is also a CERT alert somewhere out there about a possible attack
on older versions of Kerberos that use a defective PRNG.
--
Eric Lee Green Linux Subversives
[EMAIL PROTECTED] http://www.badtux.org
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Linear analysis
Date: Tue, 09 Jan 2001 03:20:06 GMT
Simon Johnson wrote:
>
> In article <[EMAIL PROTECTED]>,
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > I've read a bit about linear analysis, and I want to attempt it on
> > my hypercrypt cipher, which is available at:
> > http://users.powernet.co.uk/eton/guest/beng/hypercrypt.txt
> >
> > However, I'm having trouble seeing how to do so. I want to try and
> > find a break on reduced round (OROUNDS=1) version of hypercrypt,
> > using either the currently listed sbox (which is taken from TC5), or
> > with the AES sbox.
> >
> > Both of the sboxen I'm considering are fairly nonlinear. I fail to
> > see how to even begin doing the linear attack on even the mixing
> > component (a 4 round 16 bit fiestel), let alone on the entire
> > cipher.
> >
> > The fiestel is 4 rounds since that is the minimum number needed to
> > be secure against differential analysis.
>
> How did i know this was comming ;)
>
> I don't have the foggest how to attempt linear cryptanalysis, where
> did u find out how to do it?
Michael Scott sent me a Microsoft Word document containing a description
of differential and linear analysis on FEAL-4. The file, difflin.doc,
is 138KB. Actually, it was an assignment to implement both FEAL-4 and
the attacks on it, but it contained enough information about the attacks
to figure this stuff out.
If you want, I can send it to you.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: [EMAIL PROTECTED] (graywane)
Subject: Re: secure RNG
Date: Tue, 09 Jan 2001 03:38:12 GMT
In article <[EMAIL PROTECTED]>, Eric Lee Green wrote:
> /dev/random on Linux and (Free|Open)BSD is an interesting random number
> generator. Yarrow on Windows ( http://www.counterpane.com/yarrow if I
> remember correctly) is one for Windows.
This is not the case on OpenBSD. /dev/random is reserved for future support
of hardware random generators.
/dev/random This device is reserved for future support of hardware
random generators.
/dev/srandom Strong random data. This device returns reliable random
data. If sufficient entropy is not currently available
(i.e., the entropy pool quality starts to run low), the
driver pauses while more of such data is collected. The
entropy pool data is converted into output data using MD5.
/dev/urandom Same as above, but does not guarantee the data to be
strong. The entropy pool data is converted into output
data using MD5. When the entropy pool quality runs low,
the driver will continue to output data.
/dev/prandom Simple pseudo-random generator.
/dev/arandom As required, entropy pool data re-seeds an ARC4 generator,
which then generates high-quality pseudo-random output da-
ta. The arc4random(3) function in userland libraries
seeds itself from this device, providing a second level of
ARC4 hashed data.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Mon, 08 Jan 2001 19:59:33 -0800
DJohn37050 wrote:
> Any security proof relies on assumptions. I think the proof is random oracle,
> which some do not accept.
IOW, no proof at all of security.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
