Cryptography-Digest Digest #331, Volume #14 Fri, 11 May 01 02:13:01 EDT
Contents:
Re: 3x4 grid of triangular numbers (Robert Israel)
Re: A simple encryption algorithm based on OTP (Bill Unruh)
Re: Best, Strongest Algorithm ("Douglas A. Gwyn")
Re: Cryptanalysis Question: Determing The Algorithm? ("Douglas A. Gwyn")
Re: TC15 Design (was Bitsliced Cipher) ("Tom St Denis")
Re: TC15 Design (was Bitsliced Cipher) ("Tom St Denis")
Re: Are low exponents a problem with RSA? (David Wagner)
Re: Are low exponents a problem with RSA? (David Wagner)
Re: Tiny s-boxes (David Wagner)
More TC15 info ("Tom St Denis")
Re: Best encrypting algoritme (wtshaw)
Re: SAC'01 wannabe paper (Benjamin Goldberg)
Re: Micali-Schnorr pseudorandom bit generator (Benjamin Goldberg)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Robert Israel)
Crossposted-To: rec.puzzles,alt.math.recreational,sci.math
Subject: Re: 3x4 grid of triangular numbers
Date: 10 May 2001 23:19:21 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>Fred W. Helenius wrote:
>> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>> >Could someone direct me to Gau�'s proof that any number can be
>> >decomposed into the sum of 3 triangular numbers?
>> Section V of his _Disquisitiones Arithmeticae_. The theorem
>> is stated and proved in article 293, but the proof depends
>> upon "the preceding theory"; that is, the theory of quadratic
>> forms that he develops in the preceding 200+ pages.
>Uck. Is there any *simple* proof for this? And, how hard is it to
>decompose an arbitrary large number?
As Gauss remarks, M = x(x+1)/2 + y(y+1)/2 + z(z+1)/2 is equivalent to
8M+3 = (2x+1)^2 + (2y+1)^2 + (2z+1)^2
i.e. writing an integer congruent to 3 mod 8 as the sum of three odd
squares. Note that since the squares mod 8 are 0, 1 and 4, if an integer
congruent to 3 mod 8 is the sum of three squares they must be odd. So
it's enough to show that any integer congruent to 3 mod 8 is the sum
of three squares. LeVeque's "Fundamentals of Number Theory" suggests
in a note (after stating that the sums of three squares are all the
positive integers not of the form 4^t(8k+7)):
Somewhat simpler proofs have been found since: two of them are to be
found in Landau [Elementary Number Theory] and Mordell [Diophantine
Equations]. A proof using p-adic fields is given in Serre [A Course in
Arithmetic].
Robert Israel [EMAIL PROTECTED]
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: A simple encryption algorithm based on OTP
Date: 10 May 2001 23:20:38 GMT
In <[EMAIL PROTECTED]> "Siva Prasad Gummadi [T]" <[EMAIL PROTECTED]>
writes:
]Bill Unruh wrote:
]> Nope. That permutation must be known for the other side to use the same
]> one.
]
] That's not at all a problem, if both of them agree upon a particular
]permutation-generating program, obviously both get the same sequence of
]permuted keys
But you must assume that that program itself is available to the enemy
(unless you want to call it a secret key as well).
]> Then one knows that say bit 8 of the permuted key is the same as
]> bit 5 of the original. Thus one can do the standard attack against a
]> reused OTP.
] I don't think it is similar ro 'reusing' a key. What extrainfo, he gets
]if it is known that a particular bit is the same as in the original key?
]For that matter, let's say that you've encrypted the text using OTP. I
]can
]break that long OTP keyt into blocks of keys, each of the length same
]as my proposed key. Now, among these keys, obviously some bits do match
]at a particular place, if you consider any two 'blocks' (keys). Do you
But here given that you know the permutation program, you know
which bits are the same. You also know that the number
of 1 bits is the same in each block (they are just permuatations).
If the permutation program is a shared secret, then this becomes just an
"security through obscurity" and if the enemy ever gets one cleartext
encrypted text pair he will know the permutations (or at least a lot
about them).
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm
Date: Thu, 10 May 2001 22:45:38 GMT
"SCOTT19U.ZIP_GUY" wrote:
> ... So one can't say that blind brute force is the only way.
My point was that encryption/decryption algorithm speed is
only relevant when brute-force attack is involved, and then
it is only somewhat important. A sophisticated attack would
rarely resemble the original algorithm.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: Thu, 10 May 2001 22:48:24 GMT
Terry Ritter wrote:
> When new ciphers are frequently entering the mix, there may not *be* a
> time when "all possible" ciphers have been examined (and, thus, can be
> differentiated), simply because it is faster to use a cipher than to
> examine it.
I think what you're suggesting is that entropy be added at a
rate too great for the attacker to catch up with. Sounds familiar.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: TC15 Design (was Bitsliced Cipher)
Date: Fri, 11 May 2001 00:19:32 GMT
Also I have posted the code that analyzes the sbox. It can be used to
design and test other 4x4 sboxes...
http://tomstdenis.home.dhs.org/tc15_box.c
It's currently setup to design and analyze the box in TC15.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: TC15 Design (was Bitsliced Cipher)
Date: Fri, 11 May 2001 02:00:51 GMT
Even more changes.
I made the key schedule faster and takes less memory. You can compute the
round keys on the fly but the keysize is fixed at 128 bits. That's not a
serious problem since brute forcing 128 bits is not realistic.
So this cipher is now more suitable for embedded platforms since it's
possible to compute the round keys (given more hardware) as they are
required. The idea is that you hold the first round key and compute the R+1
round key while performing round R.
http://tomstdenis.home.dhs.org/tc15.c
As a bonus you can work the key backwards just as easily (all source
provided).
Tom
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Are low exponents a problem with RSA?
Date: 11 May 2001 02:33:28 GMT
Matthew Kwan wrote:
>Given the encryption function C = (P^e) mod n where (e,n) is
>the public key, is there any security weakness in choosing a small
>value of e?
If P is your message, without padding, there are issues. Use OAEP,
and they go away.
(There is also theoretical work which might be viewed as evidence that
RSA could be less secure with e=3 than with general e, but personally
I'm happy to stick with e=3 for the moment.)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Are low exponents a problem with RSA?
Date: 11 May 2001 02:35:10 GMT
DJohn37050 wrote:
>There are a few reasons to be concerned with using low exponent RSA.
>1) When using 3, the top HALF of the private key d is revealed, this is not a
>problem in and of itself but might be combined with another attack such as
>timing and allow the timing attacker to synchronize based on known values.
Yeah, that could happen. On the other hand, I don't know of any
timing attack that won't work just as well without the known values,
so I'm not too worried.
>2) As mentioned elsewhere, if you send the same message to the number of
>parties >= public exponent, you need to ensure that the messages are different
>in appearance.
Not an issue if you use OAEP padding.
>3) Use of a larger exponent could be considered insurance against the
>possibility of an RNG failure during formatting of the message.
How so?
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Tiny s-boxes
Date: 11 May 2001 02:36:40 GMT
Simon Johnson wrote:
>I assume it attacks the algebraic structure of the s-box?
Yes.
>Another question: Does the formation of this attack require some kind of
>precomputation, like in differential analysis where you generally have to
>generate a difference table?
No, there's no precomputation. (But your impression of differential
cryptanalysis seems to be at odds with my understanding, so maybe I didn't
understand your question.)
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: More TC15 info
Date: Fri, 11 May 2001 02:36:58 GMT
I did a linear completeness test and I found that after five applications of
the LT every output bit is a function of every input bit... tabulated below
1: 0.039062
2: 0.171875
3: 0.515625
4: 0.914062
5: 1.000000
The test program is at
http://tomstdenis.home.dhs.org/tc15_lta.c
It ignores the linear transform which actually makes the completeness
quicker....
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Best encrypting algoritme
Date: Thu, 10 May 2001 21:42:57 -0600
In article <[EMAIL PROTECTED]>, "John A. Malley"
<[EMAIL PROTECTED]> wrote:
>
> Well, let's limit ourselves to block ciphers and the question of
> chaining modes for them.
As I have said before, I don't see the great need for chaining modes. I
sometimes refer to ciphers as examples that are neither customary stream
nor customary block ciphers.
In short, everytime you encrypt the same thing, the ciphertext should
substantially vary, no IV's, not reference to adjacent blocks. To get
enough polymorphism, the length of the encrypted block will probably be
longer than the plaintext considering character set size and/or length of
the block in characters.
> What are the hallmarks of a poorer algorithm? What can we do to improve
> a block cipher algorithm that reduces or obviates the need for chaining
> modes?
Poorer algorithm blocks usually have one ciphertext from one plaintext
with one key. With the poorest of chaining modes, once the relationship
between two or a few blocks is determined, the rest can be fairly unzipped
from the remaining ciphertext. Better chaining methods at least make this
as hard as possible to do, but with more and more blocks tied together,
sufficient data for normal decryption can torpedo big or all of the
message.
I don't see a way to grossly improve algorithms that have painted
themselves in to the looking for any crutch mode help they can find. It
seems that inadequate consideration took place somewhere upstream, but all
the right questions were obviously not being asked. Surely there are many
ways to add strength as I suggest.
Better block ciphers have some sort of obvious key changes going on that
allows for increased variability; best is from an input of randomness.
The problem of reestablishing a random sequence at both ends can be
removed if the encryptive algorithm stores the path back as part of the
cipher text. Therefore, original random generation need not be
duplicated.
>
> wtshaw wrote:
> >
> > Back to one of my favorite topics, that inductive encryption is vastly
> > superior to symmetrical. If a block is reused, it is obvious in
> > symmetric.
>
> I visited your web site to read up more on inductive encryption. I
> didn't understand what's meant by "inductive".
> What does inductive mean with reference to encryption?
>
Inductive encryption means going from a specific to many, one plaintext
can yield many equivalent ciphertexts. Deductive decryption means going
from a range of equivalent but different data that can all yield a
specific root plaintext. Different randomess should affect different
blocks so that an codebook is not easily established and letting each
block present its own decryption riddle.
Consider that many ciphertext versions of the same form letter should be
totally different. Length might be the same, but there are wayus to add
random length padding as well.
> > > An All-Or-Nothing Transformation acting on the entire message is
> > > probably an example of a better single algorithm. Otherwise, there's
> > > good reason to use a block chaining mode with a block cipher.
> > >
> > > John A. Malley
> > > [EMAIL PROTECTED]
> >
> > You present only two choices when their are more. I guess it is
> > all-or-nothing thinking to shoot right past a better option. The little
> > catch that was required was that block size remain consistent, but that is
> > a snake-in-the-grass requirement meant of limit the strength of
> > algorithms. Don't get me wrong, a 2X or more increase is not needed at
> > all, just a little headroom for terrific strength to be achieved.
>
> Increasing the block size cannot prevent the attacks possible on block
> ciphers used in ECB mode. The larger size may make it harder to detect
> plaintext statistics leaking into the ciphertext but it won't prevent
> such leakage.
I agree about this as I said somewhere above. The goal is to prevent
leaking as best you can. When you bridge blocks with a predictable
manipulation, you have not added much.
>
> Preprocessing plaintext prior to encryption with a block cipher can
> help. Compressing the plaintext makes block encryption in ECB mode more
> palatable given the increase in the unicity distance when encrypting
> with the same key.
Yes, this can have some effect. It is worth the study that some are
giving it to further define it as a viable optional crypto primitive.
>
> An AONT applied to the plaintext with but a single block encrypted
> afterwards is another approach.
>
> What are some other ways to reduce or obviate the need for chaining
> modes (like CBC) when encrypting with a block cipher?
>
> John A. Malley
> [EMAIL PROTECTED]
Making algorithms overly complicated merely means that the program is apt
facilitate programming mistakes, allow hanky panky room, and hide bad
logic judgments. It is best to keep the service algorithm as transparent
as possible. While layer upon layer of primatives can be added, each
adding some keyspace, this wedding cake approach is apt to lead to a
troubling group marriage between resultant algorithms, implementers, and
users. Yes, greater strength does mean more keyspaces, but while many
layers is an alternative approch, it does not appear to be the best by
keeping the encryptive algorithm rather straight forward and easy to
understand and use.
Making each block stronger requires a great increase in key size. I have
done what looks wasteful in using huge keyspaces, but it need not be
frightful. With lots of room to play, the means of generation to fill
this keyspace becomes a bigger study that the base encryptive algorithm
itself. Indeed effective keysize can be from almost nothing to the
equivalent of tens of thousand of bits. While most want to narrowly
define keys narrowly, I don't. After all, in the ideal algorithm the
strength resides entirely in the keys; to get great strength, you need a
keyspace that is frightful for an attacker to contemplate. Keeping a
keyspace small can mean that you are running away from strength too hot to
touch for some non-scientific reason.
I am sure that I did not answer all yout concerns, but I tried. Let's
continue if you want....
--
Mother Nature always gets her revenge.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: SAC'01 wannabe paper
Date: Fri, 11 May 2001 00:52:50 -0400
In the discussion of GF multiplies...
There are such instructions as conditional assign, which could be used
to replace/avoid conditional jumps. One would use this by replacing
things like this:
if( x & 1 )
y = (y << 1) ^ p;
else
y = (y << 1) ^ 0;
with something like this:
z = ( x & 1 ) ? p : 0;
y = ( y << 1 ) ^ z;
When turning this to assembler, the assignment to z would be an
instruction something like the following:
condassign $test, $target, $source1, $source2
Where, if register $test is [==, !=, <, <=, >, >=] zero, then assign
$source1 to $target, else assign $source2 to target.
Conditional assignments can be done much faster than conditional jumps,
and they take constant time, which is another benefit.
Since I don't do much asm coding, I don't know for what architectures
this kind of instruction exists, but I'm fairly sure that there are a
number of machines which have it.
--
Shift to the left, shift to the right, mask in, mask out, BYTE, BYTE,
BYTE !!!
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Micali-Schnorr pseudorandom bit generator
Date: Fri, 11 May 2001 01:43:53 -0400
Dobs wrote:
>
> Could You please help me. I am trying to implement Micali-Schnorr
> pseudorandom bit generator. However I have a problem. In the algorithm
> there is written that:
> Yi Xi-1^e mod n
> Xi the r most significant bits of Yi
> Zi the k least significant bits of Yi
> The problem is as follow:
> Lets say that e=3, r=683, k=341, n is 1024 bits long. I select
> randomly Xo of bitlength r. I counte Y0=X1^e mod n so in fact Y0 can
> be a number between 1 and n. Let say that it has happen that Y0=5 (in
> binary: 101) Now to counte X1 we take the r most significant bits of
> Yi so in our case we take 683 bits from Y1. Our X1 will be (680 zeros
> and 101) 0000000000000000000000....00000101
> Our output Z1 will be 341 least significant bits of 101 so it will
> be (338 zeros and 101) 0000000000...00000101 so in our output apeares
> a lot of 0's. My output very often looks like this a lot of zeros
> than some mixed 1's and 0's than one more thime a lot of zeros than
> some 1's and 0's and so on and so on...
> More or less something like this:
>
00000000000000000000000000000000000000000000000000000000000000000000000000010111101101010101010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111110101010010101001101111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000110001111010101110101111000000000000000000000000000000000000000000000000000000000000000000000000
> So what about this zero's??? What to do with them, this output looks
> not like random? This zero's will always be if the bitlength of Yi
> will be less then k.
> How to solve this problem??????
If your modulus is n bits long, then you should be outputing at most
log2(n) of the least significant bits of Yi. For a 1024 bit modulus,
you should not be outputing more than log2(1024) or 10 bits at a time.
Where did you get the idea that you could use 341 bits?
Also, since the Micali-Schnorr generator seems to be similar in some
ways to the Blum-Blum-Schub generator, why not implement that, instead?
BBS is a much more well known and analysed PRNG.
One: find two large N-bit "special" numbers, p and q. Special-ness is
defined as follows:
x is special, iff (
x % 4 = 3, and
x is prime, and
(x-1)/2 is prime, and
((x-1)/2-1)/2 is prime, and
*one* more condition which I can't remember ).
Two: calculate pq. If we keep n secret, (I think) it's ok to use N=128.
This makes pq a 256 bit number.
Three: choose a random number X_0, such that 1 <= X_0 < pq
Four: test for whether this generates a short sequence, and if so, go
back to step Three.
Five: calculate the sequences of numbers
X_i = X_(i-1) ** 2 mod (pq)
Y_i = X_i mod log2(pq)
Use the Y_i values as your outputs. Note if pq is a 256 bit number,
log2(pq) is the number 256 -- this means that all Y_i values are 8 bit
numbers. Trying to use more bits of X_i without increasing the sizes of
p and q is unsafe.
Thus, the 8 lowest bits of X_i are your output bits.
If pq is sufficiently large (ie, too large to be factored (ie, is over
1024 bits)), it is perfectly safe to generate it once, and write it to
disk (even a publicly readable disk), and use it again and again and
again, without ever needing to create it anew. Of course, your X_0
values need to remain secret, and a new one is needed for each message,
but that's easy, since they need to be of no special form except to not
be on a short cycle.
--
Shift to the left, shift to the right, mask in, mask out, BYTE, BYTE,
BYTE !!!
------------------------------
** 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
******************************
