Cryptography-Digest Digest #608, Volume #12 Mon, 4 Sep 00 06:13:01 EDT
Contents:
Re: DES weak keys in 3DES (Mark Wooding)
Re: Serpent S-boxes (again) (Mack)
Re: Blum Blum Shub question (Mark Wooding)
Re: Blum Blum Shub question (Mok-Kong Shen)
Re: Inquiry (Mok-Kong Shen)
Re: Serpent S-boxes (again) (Mok-Kong Shen)
Re: Steganography vs. Security through Obscurity (Mok-Kong Shen)
Re: New cryption method... ("Stephan Leclercq")
Re: Capability of memorizing passwords (Mok-Kong Shen)
Re: Capability of memorizing passwords (jkauffman)
Re: 4x4 s-boxes (Mack)
Re: RSA public exponent (Mack)
Re: DES weak keys in 3DES (Ragni Ryvold Arnesen)
Re: Serpent S-boxes (again) (Mack)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: DES weak keys in 3DES
Date: 4 Sep 2000 09:14:25 GMT
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> Actually, if you were worried about 3DES "weak keys", it'd worry first
> about keys where either the first and second DES keys were the same,
> or the second and third keys where the same.
Yes, good point.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 04 Sep 2000 09:23:55 GMT
Subject: Re: Serpent S-boxes (again)
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Mack) wrote:
>> After an extensive search of
>> what I believe to be the correct
>> criteria of the serpent s-boxes
>> I have completed an enumeration.
>>
>> the crieria I used were as follows
>>
>> 1) Bijective
>> 2) Maximally non-linear
>
>I.e Bent.
Maximally non-linear for bijective functions.
Notice it is criteria two. In this case the
non-linearity is 4 via Rueppel's criteria.
>
>> 3) Hamming distance from one input
>> or its complement greater than or
>> equal to 6.
>
>Hamming distance between what? Between a linear vector of equal length?
Between any one equation and any one of
its inputs or its inputs complement.
>
>> 4) At most one boolean equation of order 2
>> all others of order 3.
>> 5) A one bit input change must result in
>> a two bit output change.
>> 6) Maximum XOR table entry of 4
>> 7) Maximum Linear Approxiamation Table (LAT) entry of 4
>> 8) Inverse boxes checked against properties
>> 2,3,5,6, and 7
>
>Of course #6 will hold in #8 if and only if it held originally. The
>inverse sbox will always have the same DPmax.
>
>> In the enumeration only one permutation of
>> each set of four boolean equations was checked.
>> The inverse satisfied the checked properties for
>> all tested sets. All s-boxes should have 23 more
>> permutations that are valid.
>>
>> The number of s-boxes satisfying these criteria were
>> 30720 with no equation of order 2
>> 36864 with one equation of order 2
>>
>> Only 2672 equations made up all of the
>> s-boxes.
>
>This I doubt.
Since this was an exhaustive search
It is very much true. There are only 200
equations that have order 2 and satisfy
criteria 2 and 3. There are 5280 that
have order 3 and satisfy criteria 2 and 3.
The fact that less than half of these equations
produce Serpent S-boxes really isn't terribly
suprising.
>
>> The total number of s-boxes satisfying the
>> criteria is 67584*24=1622016
>>
>> Which means only one in 12899250 (~2^23.6)
>> s-boxes satisfy the criteria.
>>
>> My conclusion is that the criteria chosen
>> (if I have understood them correctly)
>> reduce the set of s-boxes to very small set.
>
>I don't know if you are basing this on a) a guess b) empiracle testing
>or some other test. On average I can find serpent like sboxes (not
>fully) in about 8 hours. Even still at a 2^-23 prob that means there
>are about 2.5 million sboxes...
There are precisely 1622016 s-boxes that satisfy the
original Serpent criteria. This covered the entire search space.
This is not a guess it was an exhaustive search.
I have since completed the search of all 24 permutations
of the equations making s-boxes. All do indeed produce valid
s-boxes.
>
>Tom
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Blum Blum Shub question
Date: 4 Sep 2000 09:25:00 GMT
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> What do you folks think, and has anyone thought of this already?
With Y = 1, this is Rabin's public-key cryptosystem. Alone, it's
vulnerable to a chosen ciphertext attack which gives the attacker a pair
of square roots for the same quadratic residue and hence allows
factoring the modulus.
There are a number of ways of sorting this out. Using the recovered
plaintext only as a key to a `secure' symmetric cipher might help,
depending on whether the key schedule is actually good. Using OAEP to
encode the plaintext prior to encryption certainly ought to be
sufficient.
-- [mdw]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Blum Blum Shub question
Date: Mon, 04 Sep 2000 11:38:10 +0200
Benjamin Goldberg wrote:
>
> I was recently looking over how the BBS public key system works, And I
> think I might have an idea for a different way to use it.
>
> Set up your public and private keys, using all the special
> considerations for choosing your two primes.
>
> The person encrypting, chooses some X and some Y, uses X as the key to
> some secure block cipher, and sends Z=(X^2^Y mod n) (where n is the
> public BBS key), and Y. The steps of BBS decryption should be able to
> get X from Y and Z, and so we can get the key to decrypt. Y can be a
> fairly small number maybe even a constant (which would mean that it
> wouldn't need to be sent), and it would take far fewer steps to get Z
> from X than would be needed for using the BBS stream cipher to encrypt
> the entire message directly.
Sorry, I am confused. You said that Z and Y are sent and
n is public and that we can get the key (X) to decrypt.
But who are 'we'? Does that designation exclude the
opponent? Why?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Inquiry
Date: Mon, 04 Sep 2000 11:38:37 +0200
Teo Li Xi wrote:
>
> Am trying to implement a few algorithms eg. DES/IDEA/RSA in MS
> Visual C++ environment. I realise that there are many egs in the public
> domain which are written in C++, but I can't find any in VC++.
I know too little. But isn't it that any standard C++ program
should run under VC++?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Serpent S-boxes (again)
Date: Mon, 04 Sep 2000 11:38:26 +0200
Mack wrote:
>
Mok-Kong Shen wrote:
> >So the impression, if I don't err, is that there are quite
> >a number of equivalent classes of S-boxes that satisfy
> >all the criteria. This means in particular that it is
> >principally feasible to employ more S-boxes in the cipher
> >or to apply additional criteria (if these could be sensibly
> >established).
>
> It might be interesting to categorize the s-boxes
> into a number of classes and see how many are actually
> used in Serpent.
>
> On further testing ALL inverses including those of all
> permuted variants do indeed meet the same criteria.
>
> All of the serpent s-boxes meet my criteria, but
> are my criteria the ones actually used to select the serpent
> s-boxes?
You question is at the base of what I have (since some
time) criticized the documentations of some well-known
ciphers. They are not complete, i.e. don't give detailed
informations about how the design decisions are really
made, in particular how the diverse numerical values are
arrived at (and hence have a little bit in common with
snake-oils in my view, very unfortunately).
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Steganography vs. Security through Obscurity
Date: Mon, 04 Sep 2000 11:38:48 +0200
Guy Macon wrote:
>
> Mok-Kong Shen wrote:
> >I considered mainly publications of numerical data, for
> >which there is probably yet no newsgroup.
>
> [ alt.binaries.warez.ibm-pc.encrypted ]. Nobody will find
> or even notice your data there.
Fine for those who need steganography to know this.
> >Your opinion is
> >principally true, though. Suppose that there is a
> >newsgroup available that is not 'serious' (I believe in
> >fact that there are lots of them). Then one has much
> >freedom to write what is posted (which is nonsense anyway),
> >which means that it's easier to obtain good schemes to
> >conceal the secret messages. Since the communication
> >partners can operate from, say, internet cafes, tracing
> >these is practically impossible. BTW, if the partners
> >could access the internet at the same time points, then
> >another and presumably better possibility is evidently
> >a chatroom.
>
> Yoou are confusing the question of who sent the data with
> who has read it. For sending the data, internet cafes, etc.
> are equal whether it's a web page upload or a newsgroup post
> (and http://www.zeroknowledge.com/ is a better way to hide!).
> Where Usenet shines is in monitoring who reads the data.
> Web page data is at one location - easy to monitor. Usenet
> data is distributed to millions of new servers all over the
> world - much harder to monitor.
I still think that the anonymity offered by internet
cafes is suffcient. Do you have any concrete idea of
how to monitor (finding out who is the suspected person)
if you were given the job to do that? On the other hand,
I don't know whether sending a message from one's own
cite to zeroknowledge or whatever wouldn't leave a trace
behind.
M. K. Shen
------------------------------
From: "Stephan Leclercq" <[EMAIL PROTECTED]>
Subject: Re: New cryption method...
Date: Mon, 04 Sep 2000 09:30:01 GMT
Stou Sandalski <tangui [EMAIL PROTECTED]> a �crit dans le message :
JVIs5.37664$[EMAIL PROTECTED]
>
> HEY EVERYBODY I Got a sick assss crypto method... its unbreakable I
SWEAR...
> I don't really want to tell you exactly what it is, but get this... I
> [snip]
> Stou
>
I think the problem is not that he doesn't WANT to disclose the algorithm.
He CAN'T find a suitable way to describe it, the reason being probably that
he is not comfortable with exact sciences in general and math in particular
(not my opinion, he confessed). I admit it won't help him in a "sci."
newsgroup.
After much talk, I was able to "debabble" the algorithm (that's where being
a computer scientist - faced every so often with clients "explaining" in
their own terms what they want - is helpful :-). If you carefully read the
thread, you'll have it in mostly understandable form.
And after all, despite many flaws, that algorithm is not *that* bad. Hey, at
least, it's not a variation on "get a key, repeat it and xor it with the
message".
--
Stephan Leclercq - sauron <at> minasmorgul <dot> com
www <dot> minasmorgul <dot> com
S'il n'y a pas de solution, c'est qu'il n'y a pas de probl�me -- proverbe
Shadok
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Capability of memorizing passwords
Date: Mon, 04 Sep 2000 11:44:33 +0200
Benjamin Goldberg wrote:
>
> Of course, I personally think that if we're allowing arbitrary length
> passphrases, and want 128 bits of entropy in that passphrase, it would
> be much better to display a running count of the entropy of the
> passphrase textfield, and require that it have at least 128 bits of
> entropy.
A practical problem is how to compute the entropy from a
given passphrase, I suppose. Does anyone know of a method
of doing that? Thanks.
M. K. Shen
------------------------------
From: jkauffman <[EMAIL PROTECTED]>
Subject: Re: Capability of memorizing passwords
Date: Mon, 04 Sep 2000 03:23:31 -0700
In article <[EMAIL PROTECTED]>, Benjamin
Goldberg <[EMAIL PROTECTED]> wrote:
> S. T. L. wrote:
> >
> > <<I suppose not everyone knows your technique. Could
> you
> > give an example that works, i.e. automatically
> translates
> > back to the arbitrarily given 128 bit?>>
> >
> > Well, um, I'd expect that a program would be able to
> accept
> > arbitrary-length passphrases, no? Translating from
> 128 random bits to
> > a 10-word passphrase is as simple as breaking it up
> into chunks of
> > bits and looking up the words in a list of 8,192
> words (or however
> > many you have; I used 8,192 words). Doing the
> reverse would require
> > the same list.
> Wouldn't it be faster to simply hash the string for
> translating your
> text passphrase into a 128 bit value, than looking up
> the words in your
> list? I mean, having a passphrase generator as a
> seperate program seems
> like a good idea, to me. Once that's done... why
> increase the size of
> the program that uses the passphrase by including the
> list?
> Of course, I personally think that if we're allowing
> arbitrary length
> passphrases, and want 128 bits of entropy in that
> passphrase, it would
> be much better to display a running count of the
> entropy of the
> passphrase textfield, and require that it have at
> least 128 bits of
> entropy.
> This means that users can enter *any* sufficiently
> long string as a
> passphrase, so that individual users can pick things
> that are most
> easily memorizable to themselves. I might, for
> example, use "Twas
> brillig and the slithy toves did gyre and gimble in
> the wabe", which is
> something I could easily remember, since I had to
> memorize it in high
> school for something... Admittedly, a human who knows
> part of it can
> VERY easily guess the rest of it, but a computer
> couldn't, unless that
> particular poem is part of it's dictionary/database.
> If I'm worried
> about such Jabberwocky being in the cracker's
> database, because of how
> common it is, I could just choose something more
> obscure, eg "In a hole
> in the ground, there lived a hobbit." which is perhaps
> less likely to be
> in a codebreaker's dictionary. Someone who knows me,
> and what I read
> *might* be able to guess my passphrases, but a
> computer probably
> couldn't.
> --
hmmmm, sounds slightly dubious, how much entropy is there in
"To be or not to be, that is the question". As soon as one
allows users to have a say in passphrases they're going to
choose stupid ones.
* Sent from AltaVista http://www.altavista.com Where you can also find related Web
Pages, Images, Audios, Videos, News, and Shopping. Smart is Beautiful
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 04 Sep 2000 09:35:46 GMT
Subject: Re: 4x4 s-boxes
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
>> [EMAIL PROTECTED] wrote:
>> : [EMAIL PROTECTED] (Mack) wrote:
>>
>> :> bent is usually used to refer to functions which have non-linearity
>> :> which is maximum. They only occur on functions of 2n variables
>> :> and are not balanced. You appear to be refering to nearly bent
>> :> functions.
>>
>> : Ahem, according to "Perfect nonlinear Sboxes" by Kaisa Nyberg from
>> : Eurocrypt '91, we have and I quote.
>>
>> : 2. Bent Functions
>>
>> : Let q be a positive integer and denote the set of integers modulo q
>by
>> : Zq. Let "u = e^((2*pi*i)/q)" be the q'th root of unity in C, where
>i =
>> : the imaginary number sqrt(-1). Let f be a function from the set
>Zn/q
>> : of n-tuples of integers modulo q to Zq. Then the Fourier transform
>of
>> : u^f is defined as follows
>>
>> : F(w) = 1/sqrt(q^n) * sum of (x in Zn/q) (u^(f(x) - w.x), for all w
>in
>> : Zn/q.
>>
>> : Definition 2.1: A function F: Zn/q -> Zq is bent if |F(w)| = 1 for
>all
>> : w.
>>
>> : ---endquote--
>>
>> : In this case for a 4x4 function we find that "1/sqrt(q^n)"
>is "1/sqrt
>> : (2^4)" which is "1/4". Which means a WT output of '4' times 1/4
>gives
>> : us "1" and we have a bent function.
>>
>> Since your conclusion is fallacious, there must be an error in your
>> reasoning - I'll try to track it down.
>>
>> AFAICS, the quotation you provide states matters correctly - Though I
>> don't fully understand everything they say.
>
>Well read up more before posting randomness.
>
>> Then we come to your argument - which I don't follow at all.
>>
>> You seem to talk about a WT "output" of 4. The WT outputs an array of
>> values, which is often converted to a single digit in the form of a
>> non-linearity figure.
>
>I meant any element of the WT array as being a max of 4 or -4.
>Generally referred to as the LPmax.
>
umm ... the source of this conflict appears to be differing meanings
of non-linearity.
>> Bent functions have maximum non-linearity. A non-linearity of 4
>is /not/
>> the maximum possible value for a 4-input boolean function.
>
>No you are wrong, bent vectors are balanced and maximum non-linear.
>That's why they are differentiated from nonlinear vectors.
>
your definition of bent vectors is also different.
>> The maximum non-linearity of such a function is 6. This corresponds
>to a
>> WT with entries consisting entirely of +/-2. An example of the LUT of
>> such a function is: {1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1}.
>> 4 doesn't appear to come into it.
>
>Normally any figure in the WT represents the distance from 2^n where n
>is the size of the sbox (n x n). So -4/4 would be 12/20.
>
>> A bent function is one with maximum non-linearity.
>
>No it's not, at least not from my reference paper. Otherwise a value
>of 4 for the LPmax would not be bent for a 4x4 sbox (which of course it
>is).
>
only according to one definition which seems somewhat out of
kilter with the rest of the world.
>> To quote from http://www.io.com/~ritter/GLOSSARY.HTM:
>>
>> "[...] all true bent sequences, are not balanced".
>>
>> I don't see how you can evade this fact.
>
>Perhaps I misread or he misread. But I quoted the paper that actually
>defines the word. Try escaping that fact.
The paper in question is NOT the paper that defined the word 'bent'
nor 'non-linear'. O.S. Rothaus originally defined bent and R.A. Rueppel
defined the 'normal' definition of 'non-linearity' Note that there are
several definitions of 'non-linearity' however Rueppels has gained the
widest use.
>
>Tom
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 04 Sep 2000 09:50:59 GMT
Subject: Re: RSA public exponent
>Paul Schlyter wrote:
>> Bob Silverman wrote:
>> > Mack wrote:
>> > > the current recommendation is a public key length
>> > > that is greater than 1/4 the length of the modulus.
>> >
>> > No. This is the SECOND time you have made this same wrong
>> > pronouncement. It is the *private key* which must be long, and
>> > NOT the public exponent.
>>
>> He didn't claim the private key must be short, did he?
>
You are correct I did err. However I also corrected myself earlier.
>I don't think you followed the flow. Bob Silverman is
>pointing out that Mack mis-stated the current recommendation.
>
>> Why can't both the private and the public exponents be long btw?
>> Suppose I would want both the private and the public exponent
>> to be of the same length as the modulus - how would I do that?
>
>They can. The point is that given the current
>best-practice on use of RSA, the sizes you are supposing
>are slower for public key operations and have no known or
>expected security advantages.
Have no known security advantage. Yes I agree with that.
Have no expected security advantages. That I cannot agree
with. No current attack can makes the keys 257 and 65537
insecure for most common uses (there is always the boradcast
problem). But unless you have a proof to the contrary, you can't
assume that someone doesn't have a new (future) attack.
I would certainly expect larger public keys to be more resistant
than small ones. The broadcast attack certainly demonstrates
this.
>
>How would you do that? I don't understand the question.
>What is stopping you?
>
>
>--Bryan
>--
>email: bolson at certicom dot com
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: Ragni Ryvold Arnesen <[EMAIL PROTECTED]>
Subject: Re: DES weak keys in 3DES
Date: Mon, 04 Sep 2000 11:52:18 +0200
Is it possible to distinguish ciphertext produced by DES/3DES using weak
keys from any other ciphertext?
If not, then weak keys are no problem since you cannot do better than brute
force anyway.
-Ragni
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Serpent S-boxes (again)
Date: 04 Sep 2000 09:55:45 GMT
>
>
>Mack wrote:
>>
>Mok-Kong Shen wrote:
>> >So the impression, if I don't err, is that there are quite
>> >a number of equivalent classes of S-boxes that satisfy
>> >all the criteria. This means in particular that it is
>> >principally feasible to employ more S-boxes in the cipher
>> >or to apply additional criteria (if these could be sensibly
>> >established).
>
>>
>> It might be interesting to categorize the s-boxes
>> into a number of classes and see how many are actually
>> used in Serpent.
>>
>> On further testing ALL inverses including those of all
>> permuted variants do indeed meet the same criteria.
>>
>> All of the serpent s-boxes meet my criteria, but
>> are my criteria the ones actually used to select the serpent
>> s-boxes?
>
>You question is at the base of what I have (since some
>time) criticized the documentations of some well-known
>ciphers. They are not complete, i.e. don't give detailed
>informations about how the design decisions are really
>made, in particular how the diverse numerical values are
>arrived at (and hence have a little bit in common with
>snake-oils in my view, very unfortunately).
>
>M. K. Shen
>
This tends to be the problem with documentation in general.
The same person (group) produces the product and the
documentation. The net effect being that certain basic
definitions are assumed. However these definitions
are seldom universal. The problem is not limited to
ciphers it is a problem with documentation in general.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
** 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
******************************
