Cryptography-Digest Digest #308, Volume #14 Mon, 7 May 01 08:13:01 EDT
Contents:
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: Note on combining PRNGs with the method of Wichmann and Hill (Mok-Kong Shen)
Re: Best encrypting algoritme ("Tom St Denis")
Re: Cryptanalysis Question: Determing The Algorithm? ("Tom St Denis")
Re: free en/decryption library ("Tom St Denis")
Re: OAP-L3: "The absurd weakness." ("Tom St Denis")
Re: Cryptanalysis Question: Determing The Algorithm? (Mok-Kong Shen)
Re: Tiny s-boxes ("Simon Johnson")
Re: Style of discussions ("Simon Johnson")
Modification of S-Box attack ("Simon Johnson")
Re: A Question Regarding Backdoors ("Trevor L. Jackson, III")
Re: Best encrypting algoritme (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Mon, 07 May 2001 11:09:12 +0200
Mok-Kong Shen wrote:
>
> David Hopwood wrote:
> >
> > Bryan Olson wrote:
> > > The modification destroys an important property of
> > > the basic combination method: as long as the streams
> > > are independent, if any of the streams are uniform
> > > then the sum is uniform.
> >
> > Mok-Kong Shen wrote:
> > > David Hopwood wrote:
> > > > We assume that there is *at least one* uniform independent stream.
> > > > Bryan Olson's point is absolutely correct: it is obvious that the
> > > > modified Wichmann-Hill scheme, with weights that are not all
> > > > non-zero integers, does not have the property stated above.
> > > >
> > > > (Counter-example: if the only uniform stream has a weight that is not
> > > > a non-zero integer, then after weighting it is not uniform. If the
> > > > other streams are also non-uniform, then in general the sum is not
> > > > uniform either.)
> >
> > (Note that it was clear from context that "uniform" here, and in
> > Bryan Olson's post, meant uniform on [0, 1.0).)
> >
> > > In a rather early follow-up I already mentioned that from
> > > theory the result is uniform if one of the streams is
> > > uniform.
> >
> > That is obviously false. If you want a more concrete counterexample,
> > consider 1.0*r1 + 0.9*r2, where r1 is always zero and r2 is uniform on
> > [0, 1.0); clearly the result is the uniform distribution on [0, 0.9)
> > (and hence not on [0, 1.0) as would be the case if Bryan Olson's
> > property held).
>
> I am sorry that I don't understand you intention here. Do
> you have any doubt that, when BOTH r1 and r2 are non-zero,
> the above proposition is always true? If yes, please kindly
> say so and we could discuss on that. (Note that in my OP I mentioned
> that the r's are chosen in the vicinity of 1.0,
> so I was certainly not considering cases like yours.) Bryan
> Olson was refering to that known fact (a theorem) and saying
> that any deviations of the underlying assumption, namely not
> requiring that one stream is uniform, would lead to result
> that is not only (theoretically) non-reform but in fact
> can be very remote from uniform, for which Brain Gladman
> has produced a very nice experimental demonstration and I
> subsequently reproduced with another pair of PRNGs.
Sorry, I wrote wrong. I meant the coefficient of one
stream, which is uniform, is 1.0, while the coefficients
of the other streams are arbitrary.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Mon, 07 May 2001 11:27:11 +0200
Mok-Kong Shen wrote:
>
> Mok-Kong Shen wrote:
> >
> > David Hopwood wrote:
> > >
> > > Bryan Olson wrote:
> > > > The modification destroys an important property of
> > > > the basic combination method: as long as the streams
> > > > are independent, if any of the streams are uniform
> > > > then the sum is uniform.
> > >
> > > Mok-Kong Shen wrote:
> > > > David Hopwood wrote:
> > > > > We assume that there is *at least one* uniform independent stream.
> > > > > Bryan Olson's point is absolutely correct: it is obvious that the
> > > > > modified Wichmann-Hill scheme, with weights that are not all
> > > > > non-zero integers, does not have the property stated above.
> > > > >
> > > > > (Counter-example: if the only uniform stream has a weight that is not
> > > > > a non-zero integer, then after weighting it is not uniform. If the
> > > > > other streams are also non-uniform, then in general the sum is not
> > > > > uniform either.)
> > >
> > > (Note that it was clear from context that "uniform" here, and in
> > > Bryan Olson's post, meant uniform on [0, 1.0).)
> > >
> > > > In a rather early follow-up I already mentioned that from
> > > > theory the result is uniform if one of the streams is
> > > > uniform.
> > >
> > > That is obviously false. If you want a more concrete counterexample,
> > > consider 1.0*r1 + 0.9*r2, where r1 is always zero and r2 is uniform on
> > > [0, 1.0); clearly the result is the uniform distribution on [0, 0.9)
> > > (and hence not on [0, 1.0) as would be the case if Bryan Olson's
> > > property held).
> >
> > I am sorry that I don't understand you intention here. Do
> > you have any doubt that, when BOTH r1 and r2 are non-zero,
> > the above proposition is always true? If yes, please kindly
> > say so and we could discuss on that. (Note that in my OP I mentioned
> > that the r's are chosen in the vicinity of 1.0,
> > so I was certainly not considering cases like yours.) Bryan
> > Olson was refering to that known fact (a theorem) and saying
> > that any deviations of the underlying assumption, namely not
> > requiring that one stream is uniform, would lead to result
> > that is not only (theoretically) non-reform but in fact
> > can be very remote from uniform, for which Brain Gladman
> > has produced a very nice experimental demonstration and I
> > subsequently reproduced with another pair of PRNGs.
>
> Sorry, I wrote wrong. I meant the coefficient of one
> stream, which is uniform, is 1.0, while the coefficients
> of the other streams are arbitrary.
To avoid unnecessary discussions, I like to cite the following
from my answer to Bryan Olson of Mon, 16 Apr 2001 13:22:17 +0200:
I like to add something to make my last paragraph better
understandable: If one of the streams gets a factor 1.0
(and it is uniform), isn't that everything is again
(rigorously) theoretically o.k. in that particular issue?
M. K. Shen
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best encrypting algoritme
Date: Mon, 07 May 2001 10:02:14 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (Tom St Denis) wrote in
> <QThJ6.31704$[EMAIL PROTECTED]>:
>
> >
> >"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
> >news:[EMAIL PROTECTED]...
> >> [EMAIL PROTECTED] (Tom St Denis) wrote in
> >> <gDgJ6.31116$[EMAIL PROTECTED]>:
> >>
> >>
> >> >Show me a system where the value '1' (eigith bits) will map to four
> >> >different +10 byte messages and I will send you 100,000$. (Assuming
> >> >all of the entropy of the four messages is in the single byte). You
> >> >make no sense. How can you encrypt different length messages to the
> >> >same size ciphertext (except for padding upwards) when a) the
> >> >ciphertext is smaller and b) the amount of entropy in the ciphertext
> >> >is less than the plaintext.
> >>
> >> I doubt the honesty of your comment. But if you were capable of
> >> following the thread "BENNY and the MTB". Its very possible. Its a
> >> matter of fact that one could encrypt more then 256 probable messages
> >> to a one byte output file. THe output file only having the "11111111"
> >> pattern in it.
> >
> >Hmm if the output is always constant how do you tell one message from
> >another?
>
> The point is this Tom its not so much the size of the output file
> its the keyspace. If done correctly you and take a one byte file
> with a fixed value. Assume its the output value. Assume crypto system
> is my conditional compressor using A-Z and '_" that followed by
> matts BICOM.
>
> if you decrypt that single one byte fixed message "11111111"
> with Matts BICOM and then deompress with my adapticve conditional
> compressor. Your get 2**256 seperate message only in the character
> set of the condition file. Most of the file will exceed 20 characters
> in length.
My point was that if you encode two files will they both be 111111111? If
so how do you tell them apart?
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: Mon, 07 May 2001 10:02:58 GMT
"wtshaw" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <V63J6.24331$[EMAIL PROTECTED]>, "Tom St Denis"
> <[EMAIL PROTECTED]> wrote:
>
> > Hmm I can write an app to brute force any cryptosystem. That's just the
> > laws of FSMs.
>
> Easy to say but might be extremely difficult to do. If the key setup is
> time consuming, brute force is not very effective.
You're arguing the wrong point. I never said brute force would be fast, I
said it could be easily written.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: free en/decryption library
Date: Mon, 07 May 2001 10:04:21 GMT
"Jeffrey Walton" <[EMAIL PROTECTED]> wrote in message
news:3af61e8b$0$[EMAIL PROTECTED]...
> I wasn't aware those books provided libraries and APIs for Cryptographic
> Services.
>
> I have two of them, but they must be less recent than your versions.
Better
> get on Amazon or Bookpool :)
You're missing the point. If you want to write crypto apps become a
cryptographer, or at least read alot of texts to know what types of things
are wrong, etc...
> On the serious side, I'd like to see a nice WIN32 BigInt package. I've
> looked at a few out of academia (Linux/Unix), but got discouraged on the
> port.
Why win32? Why not just a portable library?
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Crossposted-To: alt.hacker,talk.politics.crypto
Subject: Re: OAP-L3: "The absurd weakness."
Date: Mon, 07 May 2001 10:06:04 GMT
"Anthony Stephen Szopa" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > "Anthony Stephen Szopa" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > With your many previous vague and less than precise posts you must
> > > explain exactly what YOU mean by "leakage."
> > >
> > > Not what "leakage" has been defined by others but in your own words
> > > what you understand this word / concept to mean.
> > >
> > > There can be no discussion on what YOU mean by "leakage" unless
> > > you define it in your own terms because you frequently are ambiguous
> > > and we cannot assume that you even know what you mean.
> >
> > Leakage means what it implies. Every output byte must leak some
(perhaps
> > little) info about the input state, this is always going to happen.
> >
> > The real question is how much info is leaked, i.e how many bytes (bits,
> > etc...) are required to learn enough about the internal state.
> >
> > Tom
>
> I think the place to start in answering this question is to read the
> Help Files: Theory, Processes, Operation, etc. and the recommended
> use.
>
> Good luck. You'll need it if you think you have a prayer in
> breaking the OTP files.
Um that's your job not mine. You want to show how secure it is, you should
come up with attacks on the system.
Tom
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: Mon, 07 May 2001 12:25:01 +0200
wtshaw wrote:
>
>[EMAIL PROTECTED] (Paul Schlyter) wrote:
>
> >wtshaw <[EMAIL PROTECTED]> wrote:
> > >
> > > Wrong. There is a infinite number of algorithms. I know of maybe a
> > > thousand and many are not talking at all.
> >
> > If you include the weak and the not well-tested algorithms -- yes!
> > However, most of those algorithms can be cracked in ways much more
> > efficient than brute force key search.
> >
> Most is an interesting word, not sure that it means much here. Aside from
> obvious cousin associations with bad incestious results, lesser algorithms
> can be compounded to produce new algorithms of any complexity. It can be
> a snowball-from-hell problem to determine what contributing algorithms are
> involved.
I am personally unable to contribute discussion materials
to the above issue but, considering it to be a non-trivial
topic, should appreciate seeing some concrete discussion
results.
M. K. Shen
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Date: Mon, 7 May 2001 12:13:52 +0100
Well, so far this tread has been damn intresting...
So i'd like to take it in the other direction, what about massive s-boxes?
Lets say we had a 64x64 s-box that could be implemented in some kind of
algebraic fashion. In order to find the XOR difference table or the
walsh-transform of the s-box would be suffiently intractable amount of work
to make cryptanalysis impossible. In which case, a cipher based on this
64x64 would be
secure from linear and diff attack after just 3 rounds. The security is not
derived from the structure of the boxes but rather the intractability of
determining the s-boxes structure.
Even if someone managed to recover the structure of the s-box it's very
likely, that at this size, that you couldn't exploit it anyway.
Of course the next question is, can we make an algebraic 64x64 s-box that
behaves as a random premutation and can not be 'decomposed' into small
s-boxes to be analysed?
I assume the answer is no because such a system would be the perfect cipher.
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: Style of discussions
Date: Mon, 7 May 2001 12:17:15 +0100
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> Time and again I read articles that contain, in my opinion,
> more or less heavy personal attacks of some writers on the
> others. I surmise that the underlying purpose of these is
> not to express any private hostility but to give certain
> emphasis to other sentences of the articles that form
> the proper scientific topics being discussed. If that is
> indeed the case, I wonder whether it wouldn't be feasible to
> find some non-personal expressions in the language to convey
> same/equivalent emphasis without causing negative psychological
> effects on the part of the persons addressed. Though being a
> foreigner with yet rather humble language competency, I am
> quite sure that English is rich/universal enough to enable
> such reformulations without much difficulty in all concievable
> situations of scientific debates. Wouldn't it be a nice thing
> that we all try a bit to keep the atmosphere of the group as
> agreeable as possible (not only for ourselves but also for
> persons who occasionally visit our group)?
>
> M. K. Shen
Yup, I agree.. However, human nature is to bicker and to squabble....
and the internet doesn't help. You can launch a personal attack against
someone with no chance of any come-back. Its a nice idea, but its wishful
thinking....
I just hope that wish comes true.
Simon.
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Modification of S-Box attack
Date: Mon, 7 May 2001 12:31:29 +0100
A lot of people use DES and/or its variants... I've not actually checked if
this would work.. but in theory it should work perfectly.
Because DES's s-box are so small, 6x4, a small change to their structure
(say the swapping of two elements of the box) has massive implications to
the effectiveness of differential and linear cryptanalysis. Thus, I propose
an aggressive attack (which in practice would probably be delivered by
Virus) where one actually swaps two of the elements in the one or more of
the DES s-boxes, in a compiled implementation.
If your clever, you'll optimise the attack to make DES as weak as possible.
Then just recover enough known plain-text to find the key (which will be a
lot less then actual DES)
A lot of ciphers can be attacked in this way. The quick fix is to make sure
encryption programs are digital signed. The reason this might help is that
it is hard to modify signature schemes into some other weak system that
still works, since most are based on maths programs.
There are problems with the attack.. If the attack is launched against a
system that encrypts files to hard-disk. After the change is made, the files
already encrypted are un-usable. Faced with this situation, most users would
re-install the encryption software, making the attack less useful.
This attack, therefore, only really applies to session keys between parties.
Making Banks etc... vulnerable.
Simon.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Mon, 07 May 2001 11:33:27 GMT
Roger Schlafly wrote:
> "Trevor L. Jackson, III" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Rick Wash wrote:
> > > No, it is not. At the very least, the US government has made some
> > > very serious proposals for backdoors into cryptosystems. For example,
> > > look at the proposed Key Escrow systems. One of the drawbacks of
> > > these systems is that they only work if everyone plays by the rules,
> > > and to get everyone to play by the rules the government will have to
> > > outlaw non-backdoored crypto. If a serious cryptographer plans to
> > > continue being a serious cryptographer, then he/she should be careful
> > > to obey the law and not end up in jail.
> > This is a questionable suggestion. Consider the conversation between
> Emerson
> > and Thoreau that ensued when Emerson visited Thoreau in jail. Emerson
> asks
> > "What are you doing in jail?", meaning that Thoreau was an unpstanding
> > citizen who could easily have avoided incarceration. In response Thoreau
> > asked "What are you doing out of jail?", meaning that the civic situation
> was
> > so dire that any citizen with integrity should be in jail.
> > In general obeying bad laws is a bad idea.
>
> Ok, civil disobedience is occasionally appropriate. But what US crypto laws
> are so dire as to justify going to jail?
>
> I'd say the worst is the DCMA, but so far there has been no enforcement
> that is worth going to jail over.
>
> (I understand the situation is worse in countries like UK and China.)
Consider the variation suggested by RW: non-backdoored crypto is outlawed.
Such a draconian restriction would present the choice of crippled crypto or
jail to anyone promoting (in the vague DCMA sense) non-bacdoored crypto. In
that situation any professional with integrity should visit jail in the
tradition of Thoreau, Parks, & Zimmerman.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best encrypting algoritme
Date: 7 May 2001 11:54:14 GMT
[EMAIL PROTECTED] (Tom St Denis) wrote in
<GouJ6.36159$[EMAIL PROTECTED]>:
>>
>> if you decrypt that single one byte fixed message "11111111"
>> with Matts BICOM and then deompress with my adapticve conditional
>> compressor. Your get 2**256 seperate message only in the character
>> set of the condition file. Most of the file will exceed 20 characters
>> in length.
>
>My point was that if you encode two files will they both be 111111111? If
>so how do you tell them apart?
>
Tom the attacker can't tell the 2 or 1000 files that encrypt to
the exact value "11111111". He has no idea. All he can do is try
different keys. to see the various files that map to "11111111"
The person who encrypts and file. Only has one piece of data the
attacker does not have. That is the key he used to encyrpt the data
so I am not sure what your getting at. Obvious if I use the
same key each file maps to something different. So for a given key
there is only one mapping to "11111111"
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
** 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
******************************
