Cryptography-Digest Digest #229, Volume #13 Sun, 26 Nov 00 19:13:01 EST
Contents:
Re: The AES MixColumn transform ("Brian Gladman")
Re: DES question: Has this ever been proven before? (Francois Grieu)
Re: Q: Encryption via modular rests (Francois Grieu)
which is the most secure algo for me? ("[T]")
Re: The AES MixColumn transform (John Savard)
Re: which is the most secure algo for me? (Francois Grieu)
Is Feistel Block Cipher With Known Key An All Or Nothing Transform? (Gary)
Re: Cryptogram Newsletter is off the wall? (Daniel James)
Re: Cyrptography Digest Archive ? (PooF)
Re: Cyrptography Digest Archive ? ([EMAIL PROTECTED])
Re: Legal issues for hobbiests (Ichinin)
Effects of successful break - a "what if"-scenario? (Ichinin)
Re: Q: Encryption via modular rests (Mok-Kong Shen)
Re: Effects of successful break - a "what if"-scenario? (Mok-Kong Shen)
Re: Cyrptography Digest Archive ? (Richard Heathfield)
Looking for implementation of GNFS ("Julie")
Re: hardware RNG's (Dan Oetting)
Data Encryption Standard ?? ("Kidkay")
Re: Data Encryption Standard ?? (John Dallman)
Re: does faster FPU and large cache improve en/decryption speed? ("CMan")
collision probability with file checksums (Ed L Cashin)
Re: hardware RNG's (David Schwartz)
----------------------------------------------------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: The AES MixColumn transform
Date: Sun, 26 Nov 2000 11:49:03 -0000
"Dido Sevilla" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Brian R. Bullock" wrote:
> >
> > I'm having trouble understanding how to accomplish the AES (Rijndael)
> > MixColumn transform without using log table lookups. Anyone with a
> > simple explanation?
> >
>
> Hopefully you have some sort of understanding of arithmetic in Galois
> Fields in the representation chosen for Rijndael. One way you can
> perform the mixcolumn transform without using log table lookups is by
> using the xtime function, which multiplies its argument by 2 in
> GF(2^8). I take it you understand that the mixcolumn, which is a
> polynomial multiplication, can be represented as multiplication of each
> column of the cipher state by a circulant matrix with coefficients 02,
> 03, 01, and 01 in GF(2^8). Note that x*02 is just xtime(x). x*03 =
> xtime(x) + x. All you need is a function that computes xtime, for which
> you can keep either a lookup table (if you want to avoid timing
> attacks), or use this C function:
>
> unsigned char xtime(unsigned char x)
> {
> x <<= 1;
> return((x & 0x80) ? x ^ 0x1b : x);
> }
This won't work because x is an 8-bit character (normally), which means that
its top bit is lost when it is shifted left. The right formulation is:
typedef unsigned char byte // must be 8 bits
byte xtime(byte x)
{
return (x << 1) ^ (x & 0x80 ? 0x1b : 0);
}
which can usually be inlined for speed.
More interestingly, since this operation has to be done on each of the four
bytes in a 32 bit word, you can use:
typedef unsigned long word // must be 32-bits
word xt_word(word x)
{
word u = x & 0x80808080;
return ((x ^ u) << 1) ^ (u - (u >> 7)) & 0x1b1b1b1b; // 2nd term could
be (u >> 7) * 0x1b
}
which is also simple enough to be inlined.
Doing this operation (and the rest of the arithmetic) on the 4 bytes in each
word in parallel speeds up the cipher significantly on low end processors
with 32 bit words. There are even faster techniques with full table
implementation as described in the Rijndael specification.
These techniques (and others) are used in my code at:
http://fp.gladman.plus.com/cryptography_technology/rijndael
Brian Gladman
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: DES question: Has this ever been proven before?
Date: Sun, 26 Nov 2000 13:46:17 +0100
David Wagner wrote:
> Francois Grieu wrote:
> >On the other hand I could use
> > f(X) = DES_k(X&0x00000000FFFFFFFF) xor (X&0x00000000FFFFFFFF)
> >and look for collisions;
>
> I think this has the same problem
Right; you figured it out before I posted my revised message.
I had thrown the idea on sci.crypt before it was mature !
Maybe it could be fixed by having an additional 2^32 bit mitmap (still
a workable 512MB) of the (low 32 bits of the) points already tested,
so that we can restart in a new cycle when an uninteresting one has
been found (after like 2^16 DES operations).
Francois Grieu
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: Q: Encryption via modular rests
Date: Sun, 26 Nov 2000 14:32:11 +0100
Mok-Kong Shen <[EMAIL PROTECTED]> asks about
> attacking encryption of plaintext through encoding it to the
> modular rests with respect to a number of suitably chosen
> (secret) co-primes ...
> It is assumed that the opponent has only known-ciphertexts
> available.
If I get you right, the secret key of your system is a set of
Kj that are coprime, and encryption of P is the set of P mod Kj.
Of course, the Chinese Remainder Theorem let the receiver knowing
the secret key recover the plaintext when 0<=P<product(Kj).
The scheme is a secret key scheme, and a very weak one.
For any P, Kj divides P - (P mod Kj) and Kj is likely to be
the GCD of the P - (P mod Kj) gathered from just a few known
plaintext/ciphertext pairs.
Francois Grieu
------------------------------
From: "[T]" <[EMAIL PROTECTED]>
Subject: which is the most secure algo for me?
Date: Sun, 26 Nov 2000 14:44:50 GMT
hi there, im looking for an encryption algo for a server program im coding,
a public key one, as it has to be reasonably fast.
which one would be the most secure one? briefly reading some doc about algos
i'd say IDEA or Blowfish, suggestions?
thanks in advanche.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: The AES MixColumn transform
Date: Sun, 26 Nov 2000 15:13:04 GMT
On Sun, 26 Nov 2000 01:38:14 GMT, brian@@@wwwebweaver.com (Brian R.
Bullock) wrote, in part:
>I'm having trouble understanding how to accomplish the AES (Rijndael)
>MixColumn transform without using log table lookups. Anyone with a
>simple explanation?
You could try my web page at
http://home.ecn.ab.ca/~jsavard/crypto/co040801.htm
where I try to make it as simple as possible.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: which is the most secure algo for me?
Date: Sun, 26 Nov 2000 16:38:29 +0100
[T] wrote:
> I am looking for an encryption algo for a server program I am
> coding, a public key one, as it has to be reasonably fast.
> Say IDEA or Blowfish, suggestions?
You mean a SECRET key encryption algorithm.
You could elect to use IDEA, or Blowfish, or Rijndael. The later
has the advantage of beeing (in the process of becoming) an official
standard (AES), and of using 128 bit blocks.
I also suggest that you have the security of the specifications
scrutinized by a professional. Lots of things can go wrong beyond
the choice of the cryptographic algorithm; for example, consider
how secure would be the storage of the key(s) on your server and
clients.
Francois Grieu
------------------------------
From: Gary <[EMAIL PROTECTED]>
Subject: Is Feistel Block Cipher With Known Key An All Or Nothing Transform?
Date: Sun, 26 Nov 2000 11:47:05 -0500
When a 'secure' Fesitel cipher is used on a block with a publicly known key
and some of the resulting block is removed. Does the bita that have been
removed have to be brute forced or is there a faster way?
So for instance is the extended block version of TEA which effectively uses
the whole file as a block an 'All Or Nothing Transform' when the key used is
known?
------------------------------
From: Daniel James <[EMAIL PROTECTED]>
Subject: Re: Cryptogram Newsletter is off the wall?
Date: Sun, 26 Nov 2000 16:58:22 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Mok-Kong Shen wrote:
> BTW, could someone
> tell whether i-button (I only know its name, never see
> one) has proved to be useful, convenient, etc. in
> practice?
One place I see iButtons in use is in bars. Everyone serving behind the
bar has a tag with an iButton embedded in it on a cord attached to
their belt, and before they ring anything up on the till they have to
press the iButton onto a reader on the corner of the till. This enables
the same till to keep track of orders being taken by several bar staff
at the same time, and also to keep a record of who serves the most in
the course of an evening. I've seen this in use in several different
pubs and bars in and around London, it seems to work well.
Cheers,
Daniel.
------------------------------
From: PooF <[EMAIL PROTECTED]>
Subject: Re: Cyrptography Digest Archive ?
Date: Sun, 26 Nov 2000 18:35:32 GMT
On Sun, 26 Nov 2000 10:57:17 +0000, Richard Heathfield
<[EMAIL PROTECTED]> wrote:
>Mark Harrop wrote:
http://lavarand.sgi.com/
<snip>
>
>o Hook up your computer to a lava lamp.
> (This has been done, by the way - A Web
> search may well reveal more information.)
>
<snip>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Cyrptography Digest Archive ?
Date: Sun, 26 Nov 2000 18:22:23 GMT
Richard Heathfield <[EMAIL PROTECTED]> wrote:
> o On some (all?) Linux systems, /dev/random might
> be worth a look. This is probably the least good
> option from this list.
Most. If memory serves very early implementations had some
problems. On the other hand, if you need a large amount of hard to
guess bits, it beats the heck out of tossing coins time-wise.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Legal issues for hobbiests
Date: Sun, 26 Nov 2000 11:53:15 +0100
Steve Portly wrote:
> ...amateur crypto hobbyist...
You would not need to worry, the "Snake oil Faq" and "the dog house"
would chop it's credibility to pieces before you could say "export
approved" :o)
/Ichinin
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Effects of successful break - a "what if"-scenario?
Date: Sun, 26 Nov 2000 12:03:39 +0100
Hi.
I have a theoretical question.
What if someone found an efficient way of finding a
flaw in an algorithm that could reduce it's complexity
from "requiring loads of time" to "searchable within
hours".
What would the possible reaction from the designer (or
corporation), potential actions etc...? The corporation
may be boasting super secure encryption and the algorithm
may be used in quite a few products.
What is the common reaction in these cases, i mean *what*
happens? Any such previous cases?
Just a theoretical question.
Thanks,
Ichinin
(.SE)
(No honestly, i have not broken anything - just curious :o)
_____________________________________________________
Not real email address, it will bounce whatsoever.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Encryption via modular rests
Date: Sun, 26 Nov 2000 20:33:36 +0100
Francois Grieu wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> > attacking encryption of plaintext through encoding it to the
> > modular rests with respect to a number of suitably chosen
> > (secret) co-primes ...
> > It is assumed that the opponent has only known-ciphertexts
> > available.
>
> If I get you right, the secret key of your system is a set of
> Kj that are coprime, and encryption of P is the set of P mod Kj.
>
> Of course, the Chinese Remainder Theorem let the receiver knowing
> the secret key recover the plaintext when 0<=P<product(Kj).
>
> The scheme is a secret key scheme, and a very weak one.
> For any P, Kj divides P - (P mod Kj) and Kj is likely to be
> the GCD of the P - (P mod Kj) gathered from just a few known
> plaintext/ciphertext pairs.
Right. But, as said, it is meant for cases where the
opponent has only known-ciphertexts.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Effects of successful break - a "what if"-scenario?
Date: Sun, 26 Nov 2000 21:01:22 +0100
Ichinin wrote:
>
> I have a theoretical question.
>
> What if someone found an efficient way of finding a
> flaw in an algorithm that could reduce it's complexity
> from "requiring loads of time" to "searchable within
> hours".
>
> What would the possible reaction from the designer (or
> corporation), potential actions etc...? The corporation
> may be boasting super secure encryption and the algorithm
> may be used in quite a few products.
>
> What is the common reaction in these cases, i mean *what*
> happens? Any such previous cases?
>
> Just a theoretical question.
My personal guess is that the situation would be comparable
to BSE in a number of European countries, where the public
was strongly assured by the politicians of the security
of (inland) beef consumption which later turned out to be
incorrect (or unfounded or whatever one likes to call it).
M. K. Shen
------------------------------
Date: Sun, 26 Nov 2000 19:59:51 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Cyrptography Digest Archive ?
[EMAIL PROTECTED] wrote:
>
> Richard Heathfield <[EMAIL PROTECTED]> wrote:
> > o On some (all?) Linux systems, /dev/random might
> > be worth a look. This is probably the least good
> > option from this list.
>
> Most. If memory serves very early implementations had some
> problems. On the other hand, if you need a large amount of hard to
> guess bits, it beats the heck out of tossing coins time-wise.
Ah, from a practical point of view I must agree with you. Even
die-rolling can be wearing after a while, and I'll take the security hit
for the sheer convenience of /dev/random.
If the NSA were after me, it might be a different matter.
But they're not.
As far as I know.
Are they?
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
------------------------------
From: "Julie" <[EMAIL PROTECTED]>
Subject: Looking for implementation of GNFS
Date: Sun, 26 Nov 2000 20:12:36 GMT
Can anyone point me to an "open source project" for
an implementation of the general number field sieve?
Any URLs or references would be greatly appreciated.
------------------------------
From: Dan Oetting <[EMAIL PROTECTED]>
Subject: Re: hardware RNG's
Date: Sun, 26 Nov 2000 14:04:13 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> If you say "unpredictable" people with think that's what you mean - not
> "containing some unpredictable element". The same with "random" - a
> stream with some random element should not be called "random" without
> qualification - or confusion is likely to result.
>
> Enough. If you want to use these terms in the way you suggest you are
> welcome to do so - provided you have clearly defined your terms.
>
> Personally, I think you'd cause less confusion if you went for a
> different term - rather than re-using a common word with what
> appears to be a different commonly accepted meaning.
ran�dom --adj. 1. lacking aim or method; purposeless;
haphazard 2. not uniform; esp., of different sizes
You did say "commonly accepted meaning". If you ment the strict
definition in the field of statistics you should have said so.
3. [Statistics] of, pertaining to, or characterizing
a set of items every menber of which has an equal chance
of occurring with a particular frequency.
------------------------------
From: "Kidkay" <[EMAIL PROTECTED]>
Subject: Data Encryption Standard ??
Date: Sun, 26 Nov 2000 21:28:47 GMT
Hello, I need to find as much information as possible on Data Encryption
Standard. I need to know it's encryption strength, hardness of deciphering,
resistance to hacker attacks, ease of development and implementation. I've
been searching all over the net, but haven't found too much information on
DES except on the RSA site. If someone recommend some books I can read or
websites I can view; I'll appreciate it. I'm learning cryptology. Thank you
in advance.
-Kidkay-
------------------------------
From: [EMAIL PROTECTED] (John Dallman)
Subject: Re: Data Encryption Standard ??
Date: Sun, 26 Nov 2000 22:20 +0000 (GMT Standard Time)
Reply-To: [EMAIL PROTECTED]
In article <jgfU5.1577$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Kidkay) wrote:
> Hello, I need to find as much information as possible on Data Encryption
> Standard. I need to know it's encryption strength, hardness of
> deciphering, resistance to hacker attacks, ease of development and
> implementation. I've been searching all over the net, but haven't
> found too much information on DES except on the RSA site. If someone
> recommend some books I can read or websites I can view; I'll
> appreciate it. I'm learning cryptology. Thank you in advance.
There's a fair amount in _Applied Cryptography_, by Bruce Schneier, and
it's a generally excellent book. There are quite a few more crypto books
reviewed at http://www.youdzone.com/cryptobooks.html
---
John Dallman [EMAIL PROTECTED]
------------------------------
From: "CMan" <[EMAIL PROTECTED]>
Crossposted-To: comp.security.pgp,comp.security.pgp.tech
Subject: Re: does faster FPU and large cache improve en/decryption speed?
Date: Sun, 26 Nov 2000 16:43:20 -0700
I don't think you can make such a broad judgment. In the case of the
Celeron, for example, the smaller cache is an advantage in certain
applications because the small on-chip cache runs at twice the speed of its
big brother the Pentium with a larger off-chip cache. For certain
applications such as brute force search of the Word/Excel key space, the
celeron with a smaller cache is actually faster at a given CPU clock speed.
In applications where a larger memory footprint is required, the overhead
associated with cache flushing could be a serious problem. Assembler
optimizations to take advantage of pipelined instructions could be more
important than simple cache size.
It really depends on the details of the application.
JK
--
CRAK Software
http://www.crak.com
Password Recovery Software
QuickBooks, Quicken, Access...More
Spam bait (credit E. Needham):
root@localhost
postmaster@localhost
admin@localhost
abuse@localhost
webmaster@localhost
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Fri, 24 Nov 2000 00:27:38 +0100, dave <[EMAIL PROTECTED]> wrote, in
> part:
>
> >If yes, to what extent? Is this very different from CPU to CPU and algo
> >to algo? Are there any commercial CPU's which are generally more
> >suitable for encryption? I'm mostly thinking about symmetric encryption
> >of large files.
>
> Large cache yes. FPU, no. But MMX is vectored integer, so it may be
> used for encryption.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Ed L Cashin <[EMAIL PROTECTED]>
Subject: collision probability with file checksums
Date: 26 Nov 2000 18:55:53 -0500
Hello. A file integrity verification product like tripwire uses
different algorithms to compute checksums for files. By comparing the
checksums of a file with known state to the current file's checksums,
it's possible to find out whether the file contents have been
modified.
If the system uses just one 160-bit algorithm, say SHA-1, for doing
the checksums, then what are the chances that an intruder could make a
malicious file that has the same checksum as the file's known-state
checksum?
I only have slightly old references at hand (Schneier 1996 and Menezes
et al. 1997) for figuring out the numbers. Using numbers from the
latter (Applied Handbook of Cryptography, p. 337), I'm trying to
figure out how secure it is to use SHA-1 all by itself to detect file
modification:
1) Attacker can do 2^80 brute-force tests
2) 160-bit digest requires 2^160 brute-force tests
3) Attack is infeasible by a long shot.
... does that hold up?
--
--Ed Cashin PGP public key:
[EMAIL PROTECTED] http://www.coe.uga.edu/~ecashin/pgp/
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: hardware RNG's
Date: Sun, 26 Nov 2000 15:59:35 -0800
Dan Oetting wrote:
> 3. [Statistics] of, pertaining to, or characterizing
> a set of items every menber of which has an equal chance
> of occurring with a particular frequency.
This is a poor description of the statistical meaning. If this were
correct, for example, no random distribution could have a mode. Every
statistician I've ever known has used 'random' to describe distributions
that were had a mode and a standard deviation. Heck, even gaussian
distributions are described as random with respect to the values of
individual members of a set whose distribution is described as gaussian.
DS
------------------------------
** 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
******************************
