Cryptography-Digest Digest #749, Volume #13 Sun, 25 Feb 01 21:13:01 EST
Contents:
Re: Rnadom Numbers ("Simon Johnson")
Re: SHA-1 (was Re: Password authentication ...) ("Henrick Hellström")
PGP key servers ("Gregory Pierce")
Re: "RSA vs. One-time-pad" or "the perfect enryption" ("Simon Johnson")
Re: OverWrite freeware completely removes unwanted files from harddrive ("Trevor L.
Jackson, III")
Re: Encrypted Email for Business Documents (phil hunt)
Re: PGP key servers (Tom McCune)
How to find a huge prime(1024 bit?) (Thomas Boschloo)
Re: Simple, possibly flawed, stream cipher (David Wagner)
Re: Improved stream cipher? (was: Re: Simple, possibly flawed, stream cipher) (David
Wagner)
Re: Super strong crypto ("Bryan Olson")
Re: Diffie-Hellman via Complex Associative Hash Functions (Jim Steuert)
----------------------------------------------------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: Rnadom Numbers
Date: Sun, 25 Feb 2001 23:12:15 -0800
Tim Tyler <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Simon Johnson <[EMAIL PROTECTED]> wrote:
>
> : Would I right in saying that if a crypto-secure pseudo-random generator
was
> : unable to be cryptanalysed until x bytes of stream were recovered then
all
> : of the bytes previous to the x'th byte must be statistically random?
[...]
>
> Unable to be cryptanalysed by who?
yeah, good point. I assume that this question cannot be answered then until
the problem surrounding p=np is solved, right? Since we can't actually
_prove_ security against all attacks until that solution is found, can we?
You see my logic is this: If any stream generator is completly unpredictable
until x bits of stream are recovered, then all the bits from 1....x-1 must
be perfectly pseudo-random.
This, i feel, is a statement of the obvious but i wondered if it could be
proved for a given algorithm.... i think i've answered my own question.
> __________
> |im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: SHA-1 (was Re: Password authentication ...)
Date: Mon, 26 Feb 2001 00:15:28 +0100
"Tim Tyler" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> What you describe would be very, very suprising. Are you using SHA1 in
> counter mode? OFB mode? If you are feeding it repeating values that
> might explain your results.
OFB - I iterated the algorithm, each time padding the previous output with
zeroes.
If you insist that you find the results "very, very surprising", I find it
equally probable (1) that I didn't perform a sufficient number of tests, or
(2) that there is a flaw in the library implementation of SHA-1 I was using.
Have you repeated the test? What were your results?
> Your results with 3DES are equally astonishing. What chaining mode are
> you using?
CBC-mode, a zero string plain-text, but only a modest number of different
keys and initialization vectors. Certainly, you could get _any_ result out
of this test, just you choose the key and plain text carefully. But a string
of zeroes seems to me as a trivial first hand choice for a chosen plain text
attack, so, yes, I agree that it would be an interesting result.
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: "Gregory Pierce" <[EMAIL PROTECTED]>
Subject: PGP key servers
Date: Sun, 25 Feb 2001 23:15:46 GMT
Hello,
I was wondering if anyone else using PGP was having trouble downloading
public keys from the mit and pgp.com key servers?
-Greg
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Sun, 25 Feb 2001 23:43:04 -0800
Sundial Services <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> S. wrote:
> > Therefore OTP:s really are unbreakable,
> > provided the pad is truly random and secret.
>
> ... which, of course, is the Achilles heel of this system in practice.
> If you cannot keep a message secret, who's to say that you'll actually
> be able to keep the one-time pad secret, and safe from Mr. Murphy's Law?
>
> The word "perfect" simply does not apply to real-world human enterprises
> of which cryptography of course is one. Conditions are never perfect;
> "ka-ka occurs," and a real system must be able to handle that.
Well, the problem is an OTP cryptosystem isn't unbreakable. Okay, in the
theortical sense it is. But people tend to forget that the secret gets
decrypted at some point, meaning it can be stollen etc.....
The only way an OTP cryptosystem could ever be 100% secure is if:
1. The secret encrypted never existed in plain-text form.
2. The OTP is unpredictable and can't be reproduced.
3. The secret was never decrypted.
and if these three conditions are met, then there is no point to it existing
anyway.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: alt.hacker
Subject: Re: OverWrite freeware completely removes unwanted files from harddrive
Date: Sun, 25 Feb 2001 23:47:48 GMT
Anthony Stephen Szopa wrote:
> Michael Brown wrote:
> >
> > <SNIP>
> > > >
> > > > I checked the web pages, but I can't find any description for how the
> > > > program ensures that the multiple overwrites actually take place. There
> > > > are several ways it could fail for a naive implementation:
> > > >
> > > > - The OS may allocate new disk blocks when writing the patterns, leaving
> > > > the old data unaltered
> > > > - The OS may cache the writes, only actually writing the last pattern to
> > > > disk (or not even that if the file is removed afterwards)
> > > > - The SCSI controller may cache the writes
> > > >
> > > > I'm interested in how you've solved this.
> > > >
> > > > Andreas
> > > >
> > > > --
> > > > Andreas Gunnarsson <[EMAIL PROTECTED]>
> > > > +46 31 7014268
> > >
> > >
> > > I don't see what you suggest could happen happening.
> > >
> > I can. My HDD has 2mb cache. Having tested various things I can shove far
> > more data that I should be able to through the HDD. In other words, it ain't
> > writing it all.
> >
> > > Give us a specific example where you have written source code that
> > > says to open a file and write to the file where the computer did not
> > > carry out this instruction.
>
> The code specifically instructs that the file to be overwritten
> is to be:
>
> opened in binary mode at the first byte
> overwritten byte by byte with the given overwrite sequence
> at the end of file the file is closed.
>
> These steps occur with each overwrite sequence pass.
>
> The code instructs the computer to do this.
>
> What you are saying is that even though the code says to do
> this that the OS will ignore this code? For example, the file
> will not be opened? Is that so?
>
> Give us an example of an OS that sane people are still using
> that ignores a hard coded instruction?
Your ignorance is showing. I'll bet you can't name a system that does not
manifest this optimization. To help you out I'll mention that all flavors
(DR/PC/MS) DOS do this under some circumstances, which means that all of the
16-bit versions of Microsoft(R) Windows (2.x,3.x,'95,'98, and ME) also do it. The
32-bit versions of Windows (NT,2000) also do this.
Consider a disk cache program that operates in write-behind mode. If a program
tells the cache to write a particular sector and then write it again before the
cache has a chance to start the first write, then the first write will never take
place. In extreme cases where a temp file is created, written, read, and removed,
the OS might never write to the disk at all.
------------------------------
From: [EMAIL PROTECTED] (phil hunt)
Crossposted-To: alt.sources.crypto,talk.politics.crypto
Subject: Re: Encrypted Email for Business Documents
Date: Sun, 25 Feb 2001 22:54:48 +0000
On Sun, 25 Feb 2001 17:58:18 GMT, Peter Harrison <[EMAIL PROTECTED]> wrote:
>On Sun, 25 Feb 2001 13:53:28 +0000, [EMAIL PROTECTED] (phil
>hunt) wrote:
>
>>If you want to write asn open source system, I wouldn't use VB as
>>that is inherently proprietary, and there is no open source implementation
>>of it.
>
>The fact is that a vast number of applications are written in VB.
True
> The
>need for a library for VB is nessasary.
Is that comment meant to logically follow from the last one?
> While I do not love MS, I am
>committed to being platform independent.
Spunds reasonable.
> My approach to this is
>probably going to be using the Delphi code to create an ActiveX for
>VB.
How platform independent is ActiveX? I'd suggest "not very".
> This is nessasary because you can't actually write ActiveX in VB.
>So there will not in fact be a 'native VB' control.
>
>>(The open source equivalent of PGP is GPG (Gnu Privacy Guard)
>>which I expect is written in C or C++.)
>
>Yes, there are Java and C implementations. There is another issue
>however - that the library will be used in commercial applications.
>By that I mean ststically linked. All my code to date is non-GPL for
>this reason. GNUPG can't be used as a DLL or anything, so is
>unsuitable.
Could it be invoked as the result of a system() call?
> To be clear, I have nothing against the GPL - its just
>that its incompatible with my objective to bring a free, open source
>solution to the world of business document interchange.
>
>>If I were you, I would also be learning towards Unix-type systems
>>rather than the proprietary Microsoft environment. Actually, I'd
>>probably use Python for all by the most processor-intensive and
>>C++ for the rest; that way I could probably get it to run on Unix/Linux,
>>Micorsoft, Mac, etc with very little difficulty porting.
>
>The sad reality is that better than 90% of the people this solution
>will be written are current Windows users.
There are a lot of windows users, true.
> The applications this is
>going to be used with are all Windows Apps.
How do you know?
> I am developing Java and
>C versions for portabil;ity to unix. I would develop Perl and Python,
>only I don't know those languages.
Python is very easy to learn, IMO.
--
*****[ Phil Hunt ***** [EMAIL PROTECTED] ]*****
"Mommy, make the nasty penguin go away." -- Jim Allchin, MS head
of OS development, regarding open source software (paraphrased).
------------------------------
From: Tom McCune <[EMAIL PROTECTED]>
Subject: Re: PGP key servers
Date: Mon, 26 Feb 2001 00:02:34 GMT
In article <Cmgm6.1523$[EMAIL PROTECTED]>, "Gregory Pierce"
<[EMAIL PROTECTED]> wrote:
>Hello,
>
>I was wondering if anyone else using PGP was having trouble downloading
>public keys from the mit and pgp.com key servers?
Yes, they are still down. But for some other keyservers:
http://www.McCune.cc/PGPpage2.htm#Servers
Tom McCune
My PGP Page & FAQ: http://www.McCune.cc
------------------------------
From: Thomas Boschloo <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: How to find a huge prime(1024 bit?)
Date: Mon, 26 Feb 2001 01:03:36 +0100
[CC-ed: to sci.crypt for a professional opinion]
An Metet wrote:
> >How to find a huge prime(1024 bit?)
>
> Select a big random number, try to divide it by small numbers
> first, then search for `Rabin-Miller´ primality test at google. If that
> fails, increase the number and repeat the above.
I would disagree, although I am no scientist.
Primes get very sparse at high numbers, but you just never know how far
appart they will be. There might be vast spaces without any primes
followed a few primes that are very near together.
If you use your proposed algorithm (and I sure as hell hope that PGP
2.6.3i doesn't use this methode), you will be more likely to hit the
first prime after a large space without primes, than you will be to hit
the prime just after that. Thus you (radically?!) reduce the maximum
ammount of primes you are likely to find.
The correct implementation would be to just generate a *new* prime from
scratch, preferably with (some) new entropy added to your pool (maybe
task-switching/runtime info?). It will be a lot slower I guess,
gathering all that entropy and calculating all those MPI random numbers.
But the resulting key will be a lot better IMHO!
> Also check out the Science->Math->Number Theory->Primes section
> while you are at google.
Hmm, maybe I can produce some high-school level proof of my
assumptions..
First: The density of primes is at average N/ln(N) from 2 until N IIRC
(where N is e.g. a 512 bit number you will need for your P and Q).
Second: Nope. I can't produce some examples at this (late) time of a few
consecutive primes above some large (chosen) number.
The Greek however proved that if you had some 'largest' prime number,
you could just multiply all primes until that prime number, add one and
then you would have created a prime that was even 'larger'. So there is
an endless supply of primes (although they may become a little far
appart or they might become hard to 'prove' to be prime).
Thomas
--
Jessica "I'm not bad, I'm just drawn that way"
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Simple, possibly flawed, stream cipher
Date: 26 Feb 2001 00:55:48 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Henrick Hellström wrote:
>Self-synchronizing does not work the way David Wagner describes it. Since x
>is always initialized to 1, state[0] is always incremented. This means that
>the value of state[0] is predetermined by it's initial value and the
>position in the stream - it will never be synchronized.
Yes, you're absolutely right. There was a bug in my post. Glad you
caught that!
But, unless I am mistaken, the attack does still work.
(albeit with complexity 256 times larger than I originally stated)
You have to guess the initial value of state[0] properly. But if you get
this guess right, then with good probability (modelling the S-box as a random
function), we will have the self-synchronizing property.
Thus, after about 4000 or so outputs, the keystream will be independent of
all but the first byte of the key. (assuming the S-box is not degenerate)
I overlooked the fact that state[0] is special and doesn't self-synchronize.
Thank you very much for the correction.
Yes, you're right that there are special S-boxes for which this attack
doesn't work, but I don't think this should be viewed as a particularly
reassuring defense. Such S-boxes are very rare, and I suspect they may
introduce other attacks. It seems that the basic structure of the
state-update function is seriously lacking in avalanche, which worries me.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Improved stream cipher? (was: Re: Simple, possibly flawed, stream cipher)
Date: 26 Feb 2001 01:06:44 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Henrick Hellström wrote:
>Here is a similar cipher that shouldn't be vulnerable to Scott Fuhler's
>attack. These are the changes:
>
>* Instead of initializing x to 1, x is initialized to state[7].
>* Instead of adding either 0 or 1 to state[i] depending on a single bit of
>x, x is added to state[i].
>* In order to prevent attacks that exploit differential relations on
>state[i], the state array is shifted up one byte and state[0] is set to the
>value of the cipher text.
I'm still left wondering about a comment I made earlier.
It appears that such a cipher requires at least 8 table
lookups per byte of output (as well as a few other very
simple operations).
How does this cipher compare in speed to, say, RC4 or
SEAL? Does anyone have any performance measurements?
If this is slower than RC4 and SEAL, is it worth spending
a lot of time on?
Also, my earlier comments about the insecurity of using
a 64-bit state still apply. With X bytes of known text,
one can break the cipher with 2^64/X work, and for X = 1MB,
this is a disconcertingly low security level. There are
also precomputation-based speedups (e.g., Hellman's
time-space tradeoff) that should not be ignored.
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Subject: Re: Super strong crypto
Date: Mon, 26 Feb 2001 01:31:36 GMT
Douglas A. Gwyn wrote:
>Bryan Olson wrote:
>> If you read my post, you'll see I was specifically asking
>> for justification for what you had written. You had a
>> "natural lifetime" for a key, somehow related to unicity
>> distance. I don't see what responding with yet another
>> unjustified proclamation is supposed to accomplish.
>
>If you had read *my* post, you might see that I wasn't
>talking about "key changes ... to limit the damage from
>exposed keys".
Obviously I read your posts: you had exactly what the quote
above says. Apparently you have no intention of justifying
what you had claimed.
I never said your were talking about "key changes ... to
limit the damage from exposed keys". I was *contrasting*
the reason modern systems change keys to the reason you
seemed to suggest.
> Others seem to have gotten the point..
As I wrote, I think David Wagner had a point that you didn't
really get. A method conjectured to fix weaknesses
conjectured to exist isn't really a result. I don't see
that you or Shaw have any justification for your insights.
--Bryan
------------------------------
From: Jim Steuert <[EMAIL PROTECTED]>
Subject: Re: Diffie-Hellman via Complex Associative Hash Functions
Date: Sun, 25 Feb 2001 20:56:01 -0500
Reply-To: Jim, Steuert
Good points. I suggested hashing because I'm not sure that
all of these functions are necessarily permutations.
As for proving that the functions are associative,
I've done that by substitution, by the c program.
Here is a concrete example, and explanation of the
construction to create even more complex associative functions.
The previous OP2 example is expressible as:
c0 = a0*b0 + a2*b3
c1 = a1*b1 + a3*b2
c2 = a0*b2 + a2*b1
c3 = a1*b3 + a3*b0
For the first equation to be associative (my search program
checks for all 4 equations), the following must hold:
y = (ab)x = a(bx)
y0 = (ab)x = (a0*b0 + a2*b3)*x0 + (a0*b2 + a2*b1)*x3
also y0 = a(bx) = a0*(b0*x0+b2*x3) + a2*(b1*x3 + b3*c0)
For this to work, * must be right and left distributive over +, and
also * must itself be associative, and + must be commutative.
In short, the operators (*,+) must be a noncommutative ring.
In so doing, the higher-level operator OP2 is associative.
The scheme is to partition the input data to be a vector of
values such as [a0 a1 a2 a3].
Some example rings to make OP2 associative
1) an integer modulo some large prime, where + and * are simply defined.
2) further break each vector element ai into 9 components such as the
9 elements of a 3 by 3 square matrix. Then the ring is the ring of
square 3 by 3 matrices modulo a prime. Thus our original vector
now has 4 dimensions of 9 parts each, or 36 parts. And it is
guaranteed to be associative. This subdivision can be continued even
further recursively with other prime moduli.
3) Another function like OP2 (I've found many of various dimensions)
4) Define + such that e + f = ( e + f -1 ) mod p
and * such that e * f = (e + f - ef ) mod p
5) break each element into ordered triples (e1,e2,e3) and (f1,f2,f3)
Then define + as (e0,e1,e2) + (f0,f1,f2) = (e0+f0,e1+f1,e2+f2) mod p
and define * as (e0,e1,e2)*(f0,f1,f2) = (e0f0,e1f0+e2f1,e2f2) mod p
Note that any input binary data (or seed) must be partitioned into
various distinct prime-modular components by a form of modular reduction.
before applying it to these functions.
I have only come up with some complex associative operators on
vector data. I have not shown that the log problem is difficult, although
I think it might be, especially with various multiple prime moduli and the
mixing involved here. I am interested if the problem of discrete logarithms
base on a generator prime-modulus matrix has been tackled, as it
relates somewhat to this problem.
As for efficiency, I will code a concrete practical example. I don't think
that this will be too complex or inefficient.
Mok-Kong Shen wrote:
> Jim Steuert wrote:
> >
> > Why can't Diffie-Hellman be accomplished using
> > associative (and balanced) hash functions? If both Alice and Bob
> > start with a common very long public initial seed, and their secret exponents are
> >
> > not so large as to compress it to nothing (an important requirement), then
> > common secret = bob's: (Seed^a)^b will equal alice's: (Seed^b)^a where
> > where a is alice's part of the secret and b is bob's part of the secret.
> > In this usage, a nesting of xor and prime-modulus associative operators
> > may work.
>
> I don't understand why do you need the concept of a 'hash
> function'. (Do you have any concrete hashing function in
> mind that works in the current context?) I suppose that what
> you require is a (general) multiplication operator (that is
> associative), as you said in your original article. If you
> choose such an operator (other than the normal one on
> integers) like the one for a vector (of integers) of your
> previous post, then I guess that you are faced with three
> tasks: (1) Prove that the operator is associative. (2) Show
> that taking the logarithm is hard. (3) Demonstrate that it
> is more efficient/economical than the scheme currently being
> used.
>
> M. K. Shen
------------------------------
** 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
******************************
