Cryptography-Digest Digest #654, Volume #9 Fri, 4 Jun 99 01:13:02 EDT
Contents:
Re: Generating Large Primes in C++ (Ralf Muschall)
Re: what cipher? (better description) (Albert P. Belle Isle)
Re: DES Effective Security Q ("karl malbrain")
Re: Generating Random Numbers ("Brian Hetrick")
Re: OTP Problems (TTK Ciar)
Re: Another source of random numbers (Bill Unruh)
Re: PGP probability of choosing primes? (Geoff Thorpe)
Re: Break this simple cipher ("Jim Keohane")
Re: Generating Random Numbers ([EMAIL PROTECTED])
Re: Generating Random Numbers (Bill Unruh)
Re: Challenge to SCOTT19U.ZIP_GUY (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
From: Ralf Muschall <[EMAIL PROTECTED]>
Subject: Re: Generating Large Primes in C++
Date: Fri, 04 Jun 1999 03:10:39 +0200
[EMAIL PROTECTED] schrieb:
> I need to generate some large primes ( 512 bit and 1024 bit ) for use
> in ElGamal... I've used the search engines and found lots of classes
Easy: Use gcc, say "include <Integer.h>" and have slow bignums.
Good: Get the CLN library by Bruno Haible (this is what
he used in his implementation of Common Lisp, which is famous
for its bignum speed (but slow otherwise)).
Ralf
------------------------------
From: [EMAIL PROTECTED] (Albert P. Belle Isle)
Subject: Re: what cipher? (better description)
Date: Fri, 04 Jun 1999 01:50:25 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 3 Jun 1999 18:52:40 -0400, "Particle" <[EMAIL PROTECTED]>
wrote:
>Thanks for the numerous responses, but I now realize I
>made the description a bit brief and not totally exact.
>
>The cipher-text has to be Exactly the size of plain-text,
>even if plain-text is 3 bytes long (or less; or more) This is
>the system restriction where I want to implement this,
>so, there is little I can do about it.
>
Pardon me for asking, but I'm curious as to how you store 3 bytes with
no overhead on a disk which can only be addressed in clusters of
512-byte sectors?
If the answer is that you do it the same way everyone else does, then
why do you care if the file-tail contains the encrypted padding
required to fill an 8-byte cipher block? (Or any other size block
which evenly divides 512?)
It would seem that it only reduces the amount of slack you have to
zeroize to prevent scavanging of RAM buffer contents into the file
tail (assuming you want a cryptosystem capable of meeting FIPS 140-1,
as opposed to a lot of so-called "encryption software" that leaks
around the encipherment).
With NTFS volume quantizations typically 4K-per-cluster, and FAT
quantizations as bad as 32K-per-cluster, it would seem that the crying
need for stream ciphers instead of block ciphers might be profitably
revisited - No?
(For transmission via TCP, there's a similar argument re TCP segment
sizes, which seldom fall below 512 bytes.)
In any case, I hope you're planning on spending most of your time
engineering the total implementation, rather than on cipher choice
(though little else seems to get discussed on this particular list, I
grant you <g>).
Albert P. BELLE ISLE
Cerberus Systems, Inc.
================================================
ENCRYPTION SOFTWARE with
Forensic Software Countermeasures
http://www.CerberusSystems.com
================================================
------------------------------
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: DES Effective Security Q
Date: Thu, 3 Jun 1999 19:07:42 -0700
Jim Gillogly <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Biham & Shamir (Differential Cryptanalysis of DES, Springer-Verlag 1993)
> show it's vulnerable to differential cryptanalysis with 2^61 chosen
> plaintexts. Not a very practical attack, but not the level of difficulty
> you want from a 56*16-bit key. See Schneier 2nd, p.295.
>
> It's certainly intuitive that it would be harmful against a differential
> fault analysis attack, since each key bit now affects only one round.
> I'd think you could recover the last-round bits almost directly, and
> work your way forward without the complication of key bits affecting
> multiple rounds.
Thanks for the reference, I'll have to obtain the book.
However, your method of <<easily>> exposing the round 16 key and working
back would also apply to <<standard>> DES as well -- presumably, you don't
even need to expose all 16 - 48 bit keys in the schedule to recover the
initial 56 key bits (and thus the remainder of the 16 keys). With
independent keys, all 16 - 48 bit keys would be required.
The problem of a chosen plaintext is not disturbing either. I'm not
constructing a BLACK BOX to be probed. As I understand this, the only
security exposure is to an obtainable quantity of known plaintext-cyphertext
pairs revealing the entire key schedule. Karl M
------------------------------
From: "Brian Hetrick" <[EMAIL PROTECTED]>
Subject: Re: Generating Random Numbers
Date: Thu, 3 Jun 1999 21:45:22 -0400
Umm, if you read the chip, as opposed to the BIOS interrupt count, the
period is about 0.8 microseconds. Of course, Windows NT and 9x slap
your hand if you try to read the chip....
[EMAIL PROTECTED] wrote in message
<7j5t3q$ee8$[EMAIL PROTECTED]>...
>Using the timing method is not always the best. Since for example in
>the PC BIOS the closest clock has a period of 55ms which is not
really
>usefull.
------------------------------
From: [EMAIL PROTECTED] (TTK Ciar)
Subject: Re: OTP Problems
Date: Fri, 04 Jun 1999 02:19:41 GMT
In article <7ip251$qcs$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
>
>Why does this let you get more than 650MB of messages? It seems like
>you would still have to worry about what might happen if you ever
>re-used a key unit -- just because they aren't next to each other doesn't
>mean that the system will be secure over time.
You're right, it would not give him >650MB. This is no different
from using blocks from your OTP sequentially. You still weaken your
security if you reuse any part of the OTP.
>oh, and by sending the offsets in the clear instead of agreeing on
>them in advance, does this ensure that an adversary will immediately
>notice re-used parts of the key ?
Yes, it does.
Something just occured to me while reading this thread -- could
you "stretch" your OTP by using it as source data for constructing
block cipher keys, and constructing each block cipher key by just
shifting through your OTP one bit at a time? It seems to me that
even though pad data is being reused, taking advantage of that re-
use would be at least as hard as breaking one unit of block cipher
encrypted data.
Clarification: say you have 1,001,024 bits of securely transported
data (your "pad" -- no longer an OTP in this context) and you're
using a symmetric 1024-bit block encryption algorithm to transmit
your secret messages. The proposed method would use bits 0..1023
to construct the first block, 1..1024 to construct the second,
2..1025 to construct the third, etc. This would seem to allow you
to transmit 1,000,000 blocks (1,024,000,000 bits' worth) of data
before running out of pad data. If you're using the pad data (P)
to mix your message text (M) thoroughally (M' = (M**f(P)) mod x, or
something similar), then there shouldn't be any correlation between
successive blocks useful to the adversary .. am I missing something?
I apologize for replying to such an old message; I haven't much
time in the day to read news these days, and I recently restarted
reading the group after a long absence.
-- TTK
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Another source of random numbers
Date: 4 Jun 1999 02:58:51 GMT
In <7j2eq7$ajq$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
]Robert Nemiroff and Jerry Bonnell who run the NASA "Astronomy Picture of
]the Day" web site ("http://antwrp.gsfc.nasa.gov/apod/astropix.html") have
]suggested using the digits of irrational numbers like Pi, e, and the
]square root of two, etc., as a source of random numbers. See Bob's page
]at "http://antwrp.gsfc.nasa.gov/htmltest/rjn_dig.html" where values of
]these numbers are given to several million decimal places.
]Is this idea widely known?
Yes, and thisis not a great source. The digits of pi can be calculated
relatively easily and thus you have a well known series here, totally
predictable, and hardly random.
------------------------------
From: Geoff Thorpe <[EMAIL PROTECTED]>
Subject: Re: PGP probability of choosing primes?
Date: Thu, 03 Jun 1999 22:46:54 -0400
Hi there,
Bob Silverman wrote:
>
> In article <7iq213$k7$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Bill Unruh) wrote:
> > mathamatical question:
> > again. Now, this would make the selection of primes which follow a long
> > stretch of non-primes much more likely that a prime with another prime
> > close by but smaller. (Teh relative probability is proportional to the
> > number of non-primes between that prime and the immediately smaller
Yep, I noticed this some time ago and talked at length with Peter
Gutmann about it (we were talking key-generation issues for Cryptlib).
This certainly is a weakness in the sense that sequential primality
checks on odd numbers does give certain primes better chances (ones
which could, in theory, one day reveal properties sometime which makes
them easier to find). Peter had a reference to an interesting paper but
unfortunately I do not have the reference anymore (I could track it down
if you REALLY need me to). The upshot of that work was that there are
theoretical results which say it is not that "critical" a problem. Ie
the entropy arguments say (in my words, not the author's) that the
entropy in sequential primality searching for primes of size "x" bits is
equivalent to the entropy in a true random primality search for primes
of size "y" bits where I think y was x*2/3 ... this is from the deep
recesses of my memory so I could be WAAAY off here.
> > prime). Does anyone know what the distribution of distances between
> > primes is for numbers of lenth L/2?
>
> No. Noone does. It is an unsolved, open, mathematical problem.
> It is known, however, that most of the prime gaps will be about
> log(L/2) (the Prime Number Theorem would be false, otherwise).
> Exceptions are rather rare. It is known, for example, that as L -->oo
> the set of primes which are preceeded by a gap less than any fixed
> power of loglog L have density 0. It is not known, however,
> how many primes are preceded by a gap of about (log L)^delta
> for delta < 1.
I'm not so sure ... I'm pretty sure I agree that there's no conclusive
result that answers all the questions, but I think there was some work
done on the probability distribution of "gaps" ... the mean of which is,
as you say, about log(L/2). And because the gaps do vary in a
non-trivial distribution, entropy is lost when doing a sequential
primality search for precisely the reason you mentioned ... so, in
theory, it is equivalent to searching for primes randomly (ie.
"properly") of a smaller size - but I don't think anyone's published any
exploitation of this ... and given the best current factoring methods,
it's hard to imagine them developing in a direction that allows them to
suddenly start "checking out primes with big gaps before them" in
preference [;-)
As it turns out, I came up with a workaround for this at the same time
as a wholesale speedup in doing the search for primes ... I was quite
excited about it until I found 2 different sources using essentially the
same idea (although I think mine was a tad cleaner). Oh well. PGP2.6.*
used sequential primality searching as far as I remember and I have no
idea if they have "fixed" this yet (the quotes are because I don't think
anybody knows if this issue is a big deal at all, even the known entropy
loss is not disastrous and it hasn't even been demonstrated to be usable
yet).
> > How much does this weaken PGP?
>
> Zero. In fact, the question assumes that an attack would depend on the size
> of the keyspace and that somehow an incremental search procedure (as used by
> PGP) reduces the size of that space in a measureable way. It would be
> impossible to measure exactly the reduction in keysapce caused by an
> incremental search procedure, but it would be TINY. Firstly, the procedure
Nope, it's definately been quantified using an entropy argument, damn I
really wish I had that reference now. And it's not "TINY" but it's not
disastrous, in fact it also provided a upper bound on the entropy loss
which is some form of comfort for the ultra-paranoid users of
sequential-search based software ... and in fact nobody knows how to
"check for primes" of this form when factoring anyway.
> really doesn't reduce the keyspace. It simply makes some keys more likely
> that others. Secondly, there are ~ 3.7 x 10^151 512 bit primes. The set of
> primes which have a low probability of being selected are only a very tiny
> fraction of these.
That depends on the distribution of the gaps ... I think it's more than
you think - Log(L/2) is just the mean, there's no reason the
distribution should be "thin". However, like you say, the sheer numbers
involved are collosal ...
> Further, a direct search attack would indeed
> depend on the size of the keyspace, But the size of the keyspace
> is SO large, that factoring attacks are much more efficient. And
> factoring attacks do not care one whit how the primes were
> generated.
True ... at least for now! But perhaps with comments like that I'm
starting to sound like one of the paranoid loonies who daily add spice
to list this newsgroup [;-)
> > Do primes which have a large distance from the next smallest prime have any
> > peculiar features that might make them more susceptible to being
> > cracked?
That happens to be my main concern with this "problem" ... I really have
no worries AT ALL that normal factoring techniques might speed up
algorithmically if its known that the prime factors are more likely to
have "big gaps" in front of them. What I AM a little worried about is
that primes that have extremely abnormal length blocks of non-primes in
front of them, exhibit desirable (for the cryptanalyst) properties.
Nobody has managed (as far as I know) to put a non-trivial upper-bound
on the size of "gaps" for numbers of "x" bits, so it's possible that
there's a large number (proportionally) of primes out there with REALLY
BIG gaps in front of them. This makes them (a) likely to turn up in
people's keys with a much higher probability than perhaps they should,
and (b) dangerous if they exhibit special properties - that would imply
that a large proportion of PGP2.6-generated RSA keys exhibit those
special properties too.
> What did you have in mind? The Number Field Sieve (the fastest
> factoring attack) only depends on the size of the number being
> factored. That the size of the modulus does not depend on
> how the primes were selected. Other, special purpose attacks
> are worse than useless on numbers of this size.
True - and I'm not really worried about the (slim) possibility of
factoring speedups from this phenomena.
> And the short answer to your question is: NO. They have
> no special features.
That is definately less certain ... People have discussed at length
prime pairs (??) where two sequential odd numbers are both prime (eg 3 &
5, 11 & 13, 17 & 19, 29 & 31, etc). Considering the opposite properties,
namely where there is a large block of sequential odd numbers that are
NOT prime would seem to me just as worth-while, and in particular highly
relevant to cryptography (or cryptanalysis more likely).
> (The average distance between primes of length L is roughly
> > ln(L), but what is the distribution?
>
> Solve that problem and win the Fields Medal.
Or get a surprise visit from the NSA [;-)
Cheers,
Geoff
------------------------------
From: "Jim Keohane" <[EMAIL PROTECTED]>
Subject: Re: Break this simple cipher
Date: Thu, 3 Jun 1999 22:51:05 -0500
The cleartext, when turned upside down, reads "i am upside down". Gee,
where's
my $5 million dollar prize? {smile} - Jim
Paul Rubin wrote in message ...
>In article <7j70qe$si0$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>>This was my point. You win the knowledge that you are not silly enough
>>to post random challenges. I posted that to see what people would
>>say. Here is the actual algorithm, '1. think of a number, 2. write it
>>in hex, 3. post as challenge'.
>>
>>Thanks for playing the game, may this be a lesson to others to post
>>algorithms not random outputs.
>
>Awww. Here is one of my favorite challenges. The ciphertext is:
>"umop apisdn we I". What is the plaintext?
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: news.groups,at.test,alt.gothic,sci.math
Subject: Re: Generating Random Numbers
Date: 4 Jun 1999 02:06:23 GMT
In news.groups Grimace <[EMAIL PROTECTED]> wrote:
: I know not the purpose. However if it's killed your original message,
: it looks like this is a mildly more sophisticated version of the
: original scam.
Does the word steganography ring a bell?
Since it's crossposted to news.groups it will be forwarded to
just about EVERY newsserver on the planet.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Generating Random Numbers
Date: 4 Jun 1999 02:45:38 GMT
In <7j5n63$b6i$[EMAIL PROTECTED]> "Andreas / Detlef Stieger"
<[EMAIL PROTECTED]> writes:
>Well, you could let the user type a random piece of text of his own choice,
>and you measure the milliseconds between the keystrokes. Using only the last
>digit of the time in milliseconds provides quite a lot random numbers.
>The good thing about this is, that, even with the same person and the same
>text, there will always be a different result.
Not a great idea, since on many machines the clock does not have
millisecond accuracy. Thus the last bits are apt to be very very
non-random. Similarly the first bits are as well. You need something
that is less than the mean difference between teh key strokes and
greater than the granularity of the clock.
Designing a good, unbiased random number generator from physical
processes is not trivial.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Fri, 04 Jun 1999 04:42:09 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tim
Redburn) wrote:
>On Thu, 03 Jun 1999 02:27:47 GMT, [EMAIL PROTECTED]
>(SCOTT19U.ZIP_GUY) wrote:
>
>>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> (Tim Redburn) wrote:
>>>On Wed, 02 Jun 1999 02:17:42 GMT, [EMAIL PROTECTED]
>>>(SCOTT19U.ZIP_GUY) wrote:
>
><snip>
>
>>>---------------------------------------------------------
>>> /* encrypts a file using 19 bit words */
>>> un32 iz, izz, i, j, ip, ipp, k, i19, i19s, jj;
>>
>> un32 is unsigned integer 32 bits in size
>
>You just don't get it, do you ?
>
>What on earth is "iz" ? Is it the distance from the earth to
>the sun, is the the number of atoms in the average human
>being ? Is it the file length in bytes, is it the file length in 19bit
>
>words, is it the result of some wierd internal calculation specific to
>
>scott19u in which case it would need more explanation ?
>
if( i19 != i19s){
pf19->a00 = 0x7ffff;
iz = geto19(ppo19, i19-1);
pf19->a00 = 0;
izz = geto19(ppo19, i19-1);
i19s += 0 == ( iz ^ izz);
;}
The above is where iz is used it really has no meaning since the inputs
and outputs of the routine are fully defined you can see that iz is derived
from things already defined. The section of code your looking at gets
executed only once per encryption the above was done to make the code
easy for some one who wants to modify the code for bit sizes other than
19bits or in case that want to rotate a different amount than 9 bits. What
this code does is to detemince if one can stay in the loop one extra time
meaning cn = E((cn-1 ^ pn) + pn+1) gets to be done one extra time. I could
have caluclated this with a different method but thought this was more
straight forward. The number if times to do the equation is a function of file
length bit field size and bit rotation amount and is differnet for different
file lenghts. To me this seemed the straight forward way to do
this but you can do it differentently.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
** 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
******************************
