Cryptography-Digest Digest #299, Volume #14 Sun, 6 May 01 06:13:01 EDT
Contents:
IQ Test (IQTaste)
LUCIFER (Ryan Sorensen)
Re: LUCIFER (Paul Rubin)
Re: LUCIFER (Ryan Sorensen)
Re: LUCIFER (Paul Rubin)
Re: Tiny s-boxes ("Henrick Hellström")
Re: Message mapping in EC. ("Cristiano")
Re: How secure is this.... (Benjamin Goldberg)
Re: Random and not random (Mok-Kong Shen)
Re: Tiny s-boxes (Tim Tyler)
Re: LUCIFER (Tim Tyler)
Re: Tiny s-boxes (Paul Rubin)
Re: LUCIFER (Ryan Sorensen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (IQTaste)
Date: 06 May 2001 05:30:17 GMT
Subject: IQ Test
www.geocities.com/iq516
------------------------------
From: [EMAIL PROTECTED] (Ryan Sorensen)
Subject: LUCIFER
Date: 6 May 2001 00:10:54 -0800
Reply-To: [EMAIL PROTECTED]
I would appreciate it if someone could point me to a paper outlining LUCIFER.
I've read the "Cryptography and Computer Privacy" article, but that wasn't
directly on LUCIFER.
If the only way I can find a paper on it, specifically "LUCIFER, A
Cryptographic Algorithm", is by purchasing the back issue of Cryptologia,
let me know.
Any other resources regarding LUCIFER would be appreciated as well.
--Ryan Sorensen
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: LUCIFER
Date: 05 May 2001 23:41:00 -0700
Typing "lucifer" and "block cipher" into Google gets almost 400 matches.
------------------------------
From: [EMAIL PROTECTED] (Ryan Sorensen)
Subject: Re: LUCIFER
Date: 6 May 2001 00:31:28 -0800
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Paul Rubin wrote:
> Typing "lucifer" and "block cipher" into Google gets almost 400 matches.
Yes, it does.
I can and did use Google.
Perhaps I should clarify.
I'm looking for a formal writeup/outline/design of the cipher.
Preferably by the team that designed it.
Most of the pages refer to the cipher as an ancestor of whatever one is being
discussed, or as an early block cipher, but nothing more.
Using google with the name of the article comes up with many many many
bibliographies and reference lists.
--Ryan Sorensen
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: LUCIFER
Date: 06 May 2001 00:17:51 -0700
I'd say look in the bibliography to Applied Cryptography (my copy is
not handy). It is very extensive and would probably have what you want,
if it exists.
Don Coppersmith described Lucifer briefly in his talk on DES at Crypto 2000.
It was a 32-bit block cipher with 128-bit keys(?), but I don't remember more.
The 32-bit block size is the part that seems amusing now.
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Date: Sun, 6 May 2001 10:34:59 +0200
"Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
news:B43J6.24319$[EMAIL PROTECTED]...
>
> "Henrick Hellström" <[EMAIL PROTECTED]> wrote in message
> news:9d25ej$462$[EMAIL PROTECTED]...
> > It might depend on how you define "generally" and "s-box", but you don't
> > suggest that a random state of RC4 would be unsafe for that reason? More
> > precisely, I mean that how safe an s-box is depends on the context of
its
> > application in the cipher algorithm. But I guess you knew that already
and
> > that you are talking about fairly conventional block ciphers.
>
> Biham proved (for example) random 6x4's are insecure for the most part in
> DES.
>
> There is nothing to suggest that random sboxes are ideal unless they are
> constrained (i.e like in Twofish).
Yes, there is: The mere number of them. 2^n < n! < n^n, so n! is of
exponential order. If the algorithm is such that it would take an attacker
with access to chosen plain text at least polynomial time to separate the
impact of each element of each s-box from the impact of any other, then I
can't see why random s-boxes can't be used.
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Re: Message mapping in EC.
Date: Sun, 6 May 2001 10:34:46 +0200
"Mike Rosing" wrote:
> Cristiano wrote:
> > This is still true if the library (I use miracl) does m=m mod p.
> > I think that this is bad because the message changes!
>
> m has to be less than p to start with or you can't get it on the curve.
> If you're embedding the data and you leave the msb clear, it's going
> to be in the range 0<m<p/2, so it's not a problem. You do give
> the opponent 1 bit of knowledge, but if your field size is large
> enough, it doesn't matter.
If m>p is it a good way split m and then sign the single m1, m2, m3...?
Cristiano
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.perl.misc
Subject: Re: How secure is this....
Date: Sun, 06 May 2001 09:07:12 GMT
This is off-topic for comp.lang.perl.misc, so please send all followups
to sci.crypt.
Dodger wrote:
> "Super-Simon" <[EMAIL PROTECTED]> wrote in message
> news:9c4oiv$lmo$[EMAIL PROTECTED]...
> > "Brett Foster" <[EMAIL PROTECTED]@home.com> wrote in message
> > news:eLkF6.96228$[EMAIL PROTECTED]...
> > > "Super-Simon" <[EMAIL PROTECTED]> wrote in message
> > > news:9c2b12$sbn$[EMAIL PROTECTED]...
> > > > Hi,
> > > >
> > > > In most security-scripts the following code is used for
> > > > encryption:
> > > >
> > > > print crypt($passwd,$salt);
> > > >
> > > > Is this safe, or at least difficult to crack, is there something
> > > > better???
> > >
> > > It is my information that once you crypt you can't go back. In
> > > other words, you cannot determin what the value of $passwd was
> > > before calling crypt.
> >
> > You mean it's a hashing-routine....
>
> No, he means it's an encryption routine.
An encryption routine transforms a plaintext into a ciphertext with the
help of a key, such that only with the key can the ciphertext be made
back into the plaintext.
A secure hashing routine transforms an input into an output, such that
it is not possible to determine the input from just the output.
The function crypt is a kind of hashing routine. The fact that its guts
were mostly stolen from an algorithm which is/was commonly used for
encryption is largely irrelevant.
Since crypt's input is limited to 8 characters (which can be easily be
brute-forced, due to it's smallness), I would recommend against using it
in writing a new application. Instead, use a modern secure hashing
algorithm, such as SHA1. You still need salt, but it gets inputed to
the hash in the same way as the key.
I would also recommend that you try to give some advice to your users
regarding the strength of their passwords. Diceware is one good way to
generate a strong password. Measuring the randomness of the string and
rejecting 'not random enough' ones is another way.
Here's a function to measure order-0 entropy (a simple measurement of
randomness):
# This [untested] function calculates
# H = Sum(i) { Pi * ( - log2(Pi) ) }}
# and returns H * length(string)
sub entropy {
my $string = shift;
my ($length, %letter) = length $string;
for( -$length .. -1 ) {
++$letter{substr($string, $_, 1)};
}
my ($x,$h) = ( ln($length), 0 );
$h += $_ * ( $x - ln($_) ) for(values $letter);
return $h / ln(2);
# some divisions ommited here and there, but they all cancel
# out, so it's ok.
}
If I've coded this right, the function returns the number of bits needed
for a non-adaptive order-0 arithmetic coder to encode the string, not
including the statistics information itself. It's a half-decent
estimate on the strength of a password/passphrase. If every letter
occurs exactly once within a string, then the entropy should measure to
be N log2 N, where N is the length of the string. Some examples are:
ab = 2 * 1 = 2
aabb = 4 * 1 = 4
abcd = 4 * 2 = 8
aabbccdd = 8 * 2 = 16
abcdefgh = 8 * 3 = 24
aaaabbbbccccdddd = 16 * 2 = 32
aabbccddeeffgghh = 16 * 3 = 48
abcdefghijklmnop = 16 * 4 = 64
As you can see, the estimator gives smaller numbers than the maximum
amount of real entropy you can have in a string that particular length,
but it's better to be safe than sorry. If you require the user to give
a password whose strength is at least 32 by this estimate, then it will
probably be strong enough for most purposes. A strength 32 password is
going to be at least 11 letters.
--
Shift to the left, shift to the right, mask in, mask out, BYTE, BYTE,
BYTE !!!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Sun, 06 May 2001 11:12:54 +0200
Paul Schlyter wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> >Paul Schlyter wrote:
> >>
> >> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >>
> >> > Given a perfect OTP source, I DO want perfect secrecy. The question
> >> > is whether I am ENTIRELY free to choose a permutation out of the
> >> > ensemble of all possible ones. IF I am ENTIRELY free, THEN by
> >> > 'definition' I CAN choose it in any way I (personally) LIKE,
> >> > including e.g. asking a friend for advise, and that without ANY
> >> > adverse effects. For otherwise I would have to take care to avoid
> >> > possible negative effects and I wouldn't be ENTIRELY free at all.
> >> > Isn't that very clear?
> >>
> >> You're not entirely free to rearrange the order of the output of your
> >> OTP source, because your personal preferences may introduce
> >> non-random components into what you'll later use for encryption.
> >> Suppose, for instance, that you picked the output from your OTP, byte
> >> by byte, and rearranged the bytes in ascending or descending order
> >> before using them for encryption, just because you personally LIKED
> >> it that way. Or, even worse, you could take the output of your
> >> perfect OTP source, bit by bit, and then rearrange the bits so you
> >> got all '0' bits first, followed by all '1' bits.... then the first
> >> half of your message would, after "encryption", remain unchanged
> >> while the second half would be XOR'ed with FFh - not a very safe
> >> way to encrypt a message!
> >>
> >> To retain the perfect secrecy of your perfect OTP source, you should
> >> not rearrange its outputs in any non-random way.
> >
> >You have apparently not closely followed the on-going
> >discussion. I was saying that it is of no effect whether
> >a message (as a whole) is encrypted by one segment
> >of OTP or by another segment, never saying anything
> >about re-arranging the bits among one and the same
> >segment. (In the latter case, of course the result will
> >e non-random in general, just consider the trivial case
> >of collecting all 0's at the front and 1's at the end!)
>
> I guess the same principle applies even for segment
> sizes larger than one bit or one byte.
>
> Or we can pick another example: suppose you ran your perfect
> OTP generator until it returned a long enough stream of
> all zeroes, and then you used that segment to encrypt
> your message because "you preferred it that way". Then
> your encryption would obviously be extremely weak. The
> reason is that you introduced a non-random element,
> essentially removing the randomness of your OTP generator.
>
> So, yes if you deliberately choose which segment of the
> OTP generator to use, there are cases when this will
> seriously weaken your encryption.
>
> It's best to let that perfect OTP generator decide what
> you should use to encrypt your messages.
To make things clear for the general readers of this thread,
I like to point out that the 'currently actual' point under
debate with Matthew Skala is a weaker form of what I hoped to
be establishable in the first post that started this debate.
As explicitly stated there, I am not very sure whether the
stronger (original) form is without logical flaws. On the
other hand, I am currently yet fairly convinced that the
weaker form of the proposition is true. Let me therefore
once again state that weaker form in detail and give a more
simple argument than what I have hithertofore put forward
to support it.
The claim is the following: Given an ideal OTP source that
deliver m bit segments S1, S2, ... Sm of equal length,
being each n bits, and given m messages M1, M2, ... Mm
of the same length, the theoretical perfect security
is unaffected by any arbitrary chosen permutation of the
m messages relative to the OTP segments.
Here is my proof: Designate the total of the m segments
by S, which is large segment from the OTP of m*n bits.
Let there be two different permutations of the messages
and denote the concatenation of the messages in the two
cases by GA and GB, which are also of length M*n bits.
Now the theory of OTP guarantees that with S I can send
a (ANY) message of m*n bits with perfect security. Since
GA is such a message, I have perfect security. Since GB
is also such a message, I also have perfect security.
M. K. Shen
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Reply-To: [EMAIL PROTECTED]
Date: Sun, 6 May 2001 09:14:23 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
:> I have the impression that it is generally thought that large s-boxes are
:> best.
:>
:> Since "Gordon, J. and H. Retkin's "Are Big S-Boxes Best?" in 1982, there
:> have been numerous studies of the properties of large s-boxes, most of
:> them showing that fraction of good s-boxes, with regard to defending
:> against linear and differential cryptanalysis, increases dramatically
:> with s-box size - and consequently, choosing an s-box at random becomes
:> increasingly safe as the size of the box grows.
: Generally this is not true. [...]
I thought that it was generally accepted. The idea is that the
probability of choosing a weak, linear s-box (if choosing at random) is
high when the box size is small, and becomes vanishingly small when the
box size becomes large. Other desirable s-box characteristics (except
small implementation size :->) also improve with the number of box inputs.
You're perfectly correct to say that large s-boxes are unlikely to be
"perfect" (in terms of maximum non-linearity, etc), but - so the
thinking goes - if you make them large enough the differences
from the ideal really don't matter, and testing them is of little
practical benefit. Indeed, if only you could make them the width of the
block, all your problems would be solved ;-)
:> However, large, random s-boxes are expensive to implement - with an nxn
:> box effectively requiring a LUT of n * 2^n bits in size. This means that
:> while a 4x4 s-box needs a 64-bit LUT, an 8x8 s-box needs a 2048 bit LUT.
: Also in software. [...]
Software is probably not where tiny s-boxes shine. I tend to try to
design for hardware - since I think today's software systems suck, and
some day not so far away, programmable logic will become ubiquitous ;-)
To be honest I haven't yet investigated in any depth how best to
implement tiny s-boxes in software.
[snip speed]
:> Now there is are well established mechanisms for building large boxes
:> from very little - except smaller boxes. For example, the field of bblock
:> cypher design contains (as a sub-field) an area known as
:> substitution-permutation networks (established over fifty years ago),
:> which is concerned largely with this.
:>
:> Also, there are now some strong cyphers that employ many iterations of
:> large numbers of very small s-boxes. The first such popular cypher that
:> I'm aware of that fits this description was GOST - and now we have Serpent
:> - which looks like an ocean of 4x4 s-boxes.
: I wouldn't include GOST in the set of "good ciphers".
I'm aware of the problems with GOST - but I needed to mention it.
Please pretend that the "strong" referred only to Serpent ;-)
: If you want some ideal ciphers with small sboxes look at Square,
: Rijndael, Twofish, DES, Serpent...
I think your idea of "small" must include 8x8 boxes...
:> The other is *tiny* s-boxes themselves [i.e.] the 3x3 s-box.
:>
:> In previous discussions I have received the impression that nobody thinks
:> the 3x3 s-box is remotely interesting - since balanced 3x3 boxes have such
:> a low maximum non-linearity - and increasing non-linearity is the major
:> function of s-boxes.
: You can have nonlinear 3x3's [...]
Yes, I'm well aware of that. Proposing that s-boxes be constructed at a
size where nonlinear boxes are an impossibility (e.g. 2x2 s-boxes) would
have been an exceptionally stupid move on my part ;-)
:> Any objection along the lines of "there are no 3x3 boxes with
:> normally-desirable s-box propertly X", need to take into
:> account the notion that a much larger number of rounds
:> can be afforded, and consequently any resulting differentials,
:> swamped.
: The problem with 3x3's is that they cannot be used to make (easily) any
: power of two function since gcd(3,2^n) is always 1 for any n.
To my mind, that's no great problem. *If* tiny s-boxes are interesting,
the fact that a few bits in every round in a 2^n bit block cypher won't
make it through one of them seems like a matter of relatively minor
concern.
You could make sure its not the same bits in each round - and
add a couple of rounds at the end to compensate.
Alternatively you could try making a fast "algebraic" 4x4 or 5x5 s-box
and use one of those instead.
[Algebraic s-boxes are a possible alternative to small boxes that
also aim to increase execution speed and reduce the area used.]
: You're right that small (i.e 4x4 => 8x8) sboxes should be used more
: often then larger ones [...]
Well, as far as I understand it, this isn't terribly widely accepted.
Large random s-boxes have something attractive about them - in that we
*know* they are ideal in many respects. By contast, making (say) a
16x16 s-box out of a whole load of 4x4 boxes in a S-P network *might*
not produce exactly the same effect.
AFAIK, we have no proofs relating to how to construct a large s-box out of
smaller ones such that the result is known to be indistinguishable from a
random permutation - if we did, block cypher design would suddenly become
a much less interesting field.
I see using large random s-boxes as a pretty safe, conservative thing to
do. While the results may not execute at top speed, we can be pretty
confident about the resulting security - and such confidence has its
place in cryptography.
: Note that "Threeway" aka 3WAY is a design that use a 3x3 sbox in bitslice
: mode ...
Thanks also to David for directing me towards 3WAY. So far I have not yet
managed to find out very much about it - besides its use of tiny boxes -
and the fact that it uses a block size that is divisible by three.
I am happy to learn that I am not the only person on the planet who has
looked twice at 3x3 s-boxes - since this means there's less chance of
it being a *completely* crazy thing to do ;-)
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: LUCIFER
Reply-To: [EMAIL PROTECTED]
Date: Sun, 6 May 2001 09:26:27 GMT
Ryan Sorensen <[EMAIL PROTECTED]> wrote:
: If the only way I can find a paper on it, specifically "LUCIFER, A
: Cryptographic Algorithm", is by purchasing the back issue of Cryptologia,
: let me know.
It's only $6, including delivery anywhere in the world - according to:
http://www.dean.usma.edu/math/pubs/cryptologia/
: Any other resources regarding LUCIFER would be appreciated as well.
John Savard's LUCIFER page:
http://home.ecn.ab.ca/~jsavard/crypto/co0401.htm
General LUCIFER description:
http://www.wisdom.weizmann.ac.il/home/albi/public_html/cryptanalysis/lect8.htm
--
__________ http://rockz.co.uk/ http://alife.co.uk/ http://hex.org.uk/
|im |yler http://atoms.org.uk/ http://mandala.co.uk/ [EMAIL PROTECTED]
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Date: 06 May 2001 02:40:02 -0700
Tim Tyler <[EMAIL PROTECTED]> writes:
> Thanks also to David for directing me towards 3WAY. So far I have not yet
> managed to find out very much about it - besides its use of tiny boxes -
> and the fact that it uses a block size that is divisible by three.
3way is described in Applied Cryptography. I don't remember much about
it, except looking over the description and noticing it needed very little
memory and was therefore a good candidate for small embedded processors.
------------------------------
From: [EMAIL PROTECTED] (Ryan Sorensen)
Subject: Re: LUCIFER
Date: 6 May 2001 03:33:02 -0800
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Tim Tyler wrote:
> Ryan Sorensen <[EMAIL PROTECTED]> wrote:
>
>: If the only way I can find a paper on it, specifically "LUCIFER, A
>: Cryptographic Algorithm", is by purchasing the back issue of Cryptologia,
>: let me know.
>
> It's only $6, including delivery anywhere in the world - according to:
> http://www.dean.usma.edu/math/pubs/cryptologia/
Oh I know, I checked it out. It's not so much the cost as the timeframe.
>: Any other resources regarding LUCIFER would be appreciated as well.
>
> John Savard's LUCIFER page:
> http://home.ecn.ab.ca/~jsavard/crypto/co0401.htm
>
> General LUCIFER description:
> http://www.wisdom.weizmann.ac.il/home/albi/public_html/cryptanalysis/lect8.htm
Thank you very much.
--Ryan Sorensen
------------------------------
** 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
******************************
