Cryptography-Digest Digest #262, Volume #13 Sat, 2 Dec 00 23:13:01 EST
Contents:
Re: Newbie (Tom St Denis)
Re: Revised cipher (Tom St Denis)
Re: JOB: Software Engineer : Security - Ohio (Jeffrey Williams)
Re: I need to crack a key ("r.e.s.")
Re: On mutation of crypto algorithms (David Hopwood)
Re: collision probability with file checksums (David Hopwood)
What's better CAST in PGP or Blowfish 128bit? ("Noname")
Re: On mutation of crypto algorithms (Tom St Denis)
Re: I need to crack a key (Tom St Denis)
Re: I need to crack a key (Steve Portly)
Re: What's better CAST in PGP or Blowfish 128bit? (Tom St Denis)
Re: Newbie ("Michael")
Re: Newbie ("Michael")
Re: Newbie ("Michael")
Re: Newbie ("Michael")
Re: The AES MixColumn transform (Brian R. Bullock)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Newbie
Date: Sun, 03 Dec 2000 01:28:05 GMT
In article <QhfW5.84973$[EMAIL PROTECTED]>,
"Michael" <[EMAIL PROTECTED]> wrote:
>
> "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> news:90au05$5ic$[EMAIL PROTECTED]...
> > In article <9L%V5.84224$[EMAIL PROTECTED]>,
> > "Michael" <[EMAIL PROTECTED]> wrote:
> > > I would think a (fast) computer would be perfect for brute
forceing
> > it.
> > > But, I have no concept of just how fast the computers 'they' have
are.
> > > Mine is not up to the task!
> > >
> > > I once (when I had a P200) wrote a program to attempt a brut force
> > decode of
> > > a simple message.
> > > It was going so slow I added code to estimate (based on progress)
how
> > long
> > > it would take to finish.
> > > It was MANY YEARS! I gave up.
> > > Not exactly practical.
> > >
> > > Thanks for the reply,
> >
> > Your concept of "fast computers" completely baffles me. A 500mhz
> > Athlon computer (I think that is what you said you have) is capable
of
> > about 1.5 billion instructions per second (maximum) and would
average
> > about 500 million (assuming well written code, etc). Compare that
to a
> > 286 from 15 years ago... (286's ran at about 16mhz tops).
> >
> > Normally brute force is NOT the way to attack an algorithm. DES for
> > example can be broken in theory by an attack faster then brute
force.
> > It just happens for short key algorithms such as DES it is more
> > practical today to brute force the key.
> >
> > Often brute forcing is done on a cluster of computers (a DES key
would
> > takes months on a Atlhon 500) to linearly increase the search rate.
> > distributed.net is a good example of such.
> >
> > Tom
> >
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
> >
>
> 1.5 Billion IPS. OK. What would you estimate the BEST the NSA can
do on a
> priority 1 job?
The NSA is most likely the proud owner of several thousand 1ghz
(probably upwards of 1GIPS) computers. I wouldn't say they have the
enterprise computer though.
For the most part brute forcing is not what the NSA would do anyways.
More often then not poorly implemented (or home-brew crypto) crypto is
the source of security leaks. If for example you have this magic
crypto bubble and you use something like CAST with a 128-bit key then
there would not be a chance in heck that you find the key before your
great-great-great-great-great-great grandkids finish university.
However, real applications exist outside the "magic crypto bubble" and
are subject to often very unorthadox attacks (cramped RNGs for example).
Currently distributed.net (a league of about 100,000 computers) has
been clunking away on a 64-bit key for two years and is only 35% or so
done. A 80-bit key is 65536 times harder and a 128-bit key is
18,446,744,073,709,551,616 times harder.
Obviously brute force is not the means of attack the NSA (or
any "cracker") would choose.
Tom
N.B the distinction between "cracker" and "hacker" is chosen. A hacker
is someone who researches security related devices/applications to
learn and hopefully help others. A cracker is someone with enough
brains to double click on a program to perform malicous acts....
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Revised cipher
Date: Sun, 03 Dec 2000 01:30:34 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> I've done a bit of rewriting on the cipher I recently sent to this
NG.
> I've added a key schedule, and written the decryption function.
>
> I'd like some suggestions on how to do differential cryptanalysis,
> though. I've chosen 3 rounds, arbitrarily, so that I can test it, and
> so that analysis can be done, but I'm certain that that's not enough.
>
> Also, I've no idea how strong the key schedule is; I think it's
> reasonably strong, but I'm not certain how to analyse it.
May I suggest two things:
1. Post pseudo-code or algorithmic descriptions
2. Post source code on your website only?
This will save bandwidth and help others analyze your design much
faster. More often then not if you spend a few hours typing up a brief
paper and print it to PostScript as a file more people will be able to
read it.
Make sure if you do explain it that you explain the choices for all the
primitives and the overall design. It is not enough to mention what
you do in your cipher, you have to say why.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Subject: Re: JOB: Software Engineer : Security - Ohio
Date: Sat, 02 Dec 2000 19:43:14 -0600
Good comments. If they're followed, you've probably helped. But I cannot
help but wonder if [EMAIL PROTECTED] reads this NG. My expectation
would be NOT, or she'd probably have done a better job at writing a job
description.
Keep in mind that, all to frequently, job descriptions are written by HR
types who have, at best, a poor idea of the qualifications required to do
the job. It's likely a case of "we'll know what we need when we see it".
Bob Silverman wrote:
> In article <908g0a$9vf$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > Our client is growing and as a result has a need for a talented,
> > Software Engineer who has some expertise in Software Security and
> > Cryptography.
> >
> > This is a senior level software and systems engineering position. The
> > individual will be responsible for the investigation and
> implementation
> > of such software and hardware components that ensure the secure
> > transfer and storage of sensitive financial institution and individual
> > customer data. This will include, but not be limited to, transfer and
> > holding of customer PIN's cryptography keys and algorithms. The
> >
>
> > on current industry trends, to various internal software groups. Will
> > ensure that algorithms and techniques used for data security meet
> > government and industry standards specifications.
>
> So you need someone who knows FIPS standards as well. Why don't
> you mention this in your list of required qualifications? This
> is much more important than knowing an OS or language {which
> you do specify)
>
> >
> > Qualifications
> > * A BSEE or BSCS or equivalent degree with 5 to 7 years of
> > programming experience
> > * Experience in cryptography and other PC security projects
> > * Experience with data communications standards and trends
> > * Experience with C, C++ and general software and system
> > development practices
> > * Experience in Windows NT, Windows 98, OS/2 required, Linux and
> > Unix helpful
>
> Your "requirements" are totally screwed up and show that you and
> you client do not really understand the skills need for such a job.
> Issues surrounding secure storage of PINS calls for deep understanding.
> Someone with "some experience" isn't who you want for this.
>
> You need a security expert. "some experience" won't cut it.
> Further, mentioning a specific language/platform/OS, etc. is ridiculous.
> The person you need will have such knowledge or can easily acquire it.
> What you need is someone with deep skills in computer science and
> expertise in security.
>
> Period.
>
> Such a person may be automatically assumed to have the coding
> skills needed for the job.
>
> And why "5 to 7 years" experience? Are you afraid you might have to
> pay someone with more experience more than you are willing to pay?
>
> You won't find someone with "5 to 7 years" experience who has the
> required security background.
> --
> Bob Silverman
> "You can lead a horse's ass to knowledge, but you can't make him think"
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: I need to crack a key
Date: Sat, 2 Dec 2000 17:44:19 -0800
"Tom St Denis" <[EMAIL PROTECTED]> wrote ...
[...]
| Only lower case chars:
| 1. Length of 7 chars, # of keys = 8,031,810,176 (2^33)
| 2. Length of 14 chars, # of keys = 64,509,974,703,297,150,976
(2^65)
[...]
| Lower+Upper
| 1. Length of 7 chars, # of keys = 1,028,071,702,528 (2^40)
| 2. Length of 14 chars, # of keys =
1,056,931,425,538,820,521,590,784
| (2^80)
Sorry to nitpick, but ...
n 2^n
==============================
33 8589934592
40 1099511627776
65 36893488147419103232
80 1208925819614629174706176
-r.e.s.
------------------------------
Date: Sun, 03 Dec 2000 01:45:44 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: On mutation of crypto algorithms
=====BEGIN PGP SIGNED MESSAGE=====
Tom St Denis wrote:
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > Tom St Denis wrote:
> > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > > An interesting question is how would a scaled-down version
> > > > of Rijndael compete with DES. My feeling of the gut is that
> > > > 20 rounds would probably suffice to provide a fairly safe
> > > > bet.
> > >
> > > Irrelevant. Rijndael cannot process 64-bit blocks. The closest
> > > thing is a 72-bit block.
> >
> > What hinders a scaling-down to 64 bit blocks?
>
> The fact that you cannot build a square with eight elements...
The Rijndael state doesn't have to be square. Either a 2x4 array
(Nb = 2, word size 4 bytes, and shift offsets C1 = 1, C2 = 0, C3 = 1,
for example) or a 4x2 array (Nb = 4, word size 2 bytes, C1 = 1) appear
to work.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOilTfTkCAxeYt5gVAQHkiwf8C56lSyTy80XB1nDWljpIdUhK2ZBMiXYB
q+028Ue4iXhkv0sGkoWJYyTzoJZ3w4Zyv4c5ocD/CffypkPywGB1XP+UAHihHw/F
UiotLSm8wzEAy/qsSalvHxJJTxjJRXtC95PDPXe4N7uD30W5JWMiHp57e+BCLsbM
fpQhE75MjxSzX2ENhWDY+lt3nwkWZW3x0708Yz9OxjPG8KPfmLI+4N9Ozie34TiQ
9+a3jObadKQ5sGnKLeIhM7/lws7SS6bN7+6lT91UZjzHK7JImpKj+bNzzj2ZQIGj
BJya6JyeNY/MALxME0ZvJrd4QJvFq+d0kkjqGA0sSi1RTo7hs3XH5Q==
=UdRM
=====END PGP SIGNATURE=====
------------------------------
Date: Sun, 03 Dec 2000 01:46:21 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: collision probability with file checksums
=====BEGIN PGP SIGNED MESSAGE=====
Ed L Cashin wrote:
> The whole issue, though, once again begs the question: is it any
> harder to find a collision pair (birthday attack with 2^(n/2)
> difficulty) when one of the files must do something useful? Or is it
> just as easy, since you make the malicious part of the file and then
> manipulate the checksum by changing some meaningless padding in the
> file?
For a generic birthday attack it is just as easy, for the reason you
suggest (assuming that the file format allows for padding, which it
almost certainly will do).
For an attack that exploits a flaw in the hash function, there is no
guarantee that it will be as easy, but in practice it probably will be.
This is especially true for Merkle-D=E5mgard hashes (i.e. almost all hash=
es
in common use), where the attack exploits a flaw in the compression
function.
- -- =
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 0=
1
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has b=
een
seized under the Regulation of Investigatory Powers Act; see www.fipr.org=
/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOilZYTkCAxeYt5gVAQHtHAgAxQm6FlOHc/eSfN73Z9bd6FEXjcMIgZiW
OkY7jCp2Hq+E9uWBNbP6JllmoeKGBjqM2GYRpQ341imbB+rcQQWEkhWlh0cvfMWt
ooZ80cBOHTPUF/s4aQVZ/4iyGz84icaSVx+9AjpuuXxZFi3fpiMmJmp2wdTkpOmr
L/OLUqQyQsyU4I1tI/krlu+mwM4IOWNH0xWwv2EEw1TS6zCxHCz9BVnSEtWr5Iwt
dvS2BZbNM4g5YGL8PLwTEmz9Q4T4fk+zZFETEQLcOIbz2ahcGiiIgbrBjuaVTkW7
vCXCicoPxYsTaMC4Tiyvl09CVps/30LM/4dh25zSDF2aXzHnTU3feA=3D=3D
=3D2jOB
=====END PGP SIGNATURE=====
------------------------------
From: "Noname" <[EMAIL PROTECTED]>
Subject: What's better CAST in PGP or Blowfish 128bit?
Date: Fri, 1 Dec 2000 22:36:09 +0100
Hi all!
What is better? CAST in PGP or Blowfish 128bit.
Does anywhere exists freeware program with new and strong algorithm?
Thx.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: On mutation of crypto algorithms
Date: Sun, 03 Dec 2000 02:28:16 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
>
> Tom St Denis wrote:
> > In article <[EMAIL PROTECTED]>,
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > Tom St Denis wrote:
> > > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > > > An interesting question is how would a scaled-down version
> > > > > of Rijndael compete with DES. My feeling of the gut is that
> > > > > 20 rounds would probably suffice to provide a fairly safe
> > > > > bet.
> > > >
> > > > Irrelevant. Rijndael cannot process 64-bit blocks. The closest
> > > > thing is a 72-bit block.
> > >
> > > What hinders a scaling-down to 64 bit blocks?
> >
> > The fact that you cannot build a square with eight elements...
>
> The Rijndael state doesn't have to be square. Either a 2x4 array
> (Nb = 2, word size 4 bytes, and shift offsets C1 = 1, C2 = 0, C3 = 1,
> for example) or a 4x2 array (Nb = 4, word size 2 bytes, C1 = 1) appear
> to work.
Wouldn't it have to be a 4x2 to work? The C(x) column transform is a
4x4 MDS is it not?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: I need to crack a key
Date: Sun, 03 Dec 2000 02:25:45 GMT
In article <90c8id$idj$[EMAIL PROTECTED]>,
"r.e.s." <[EMAIL PROTECTED]> wrote:
>
> "Tom St Denis" <[EMAIL PROTECTED]> wrote ...
> [...]
> | Only lower case chars:
> | 1. Length of 7 chars, # of keys = 8,031,810,176 (2^33)
> | 2. Length of 14 chars, # of keys = 64,509,974,703,297,150,976
> (2^65)
> [...]
> | Lower+Upper
> | 1. Length of 7 chars, # of keys = 1,028,071,702,528 (2^40)
> | 2. Length of 14 chars, # of keys =
> 1,056,931,425,538,820,521,590,784
> | (2^80)
>
> Sorry to nitpick, but ...
>
> n 2^n
> ------------------------------
> 33 8589934592
> 40 1099511627776
> 65 36893488147419103232
> 80 1208925819614629174706176
I truncated the fractions... my point was that there are lots of keys...
(e.g 26^14 ~ 2^65.8 ~ 2^65)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: I need to crack a key
Date: Sat, 02 Dec 2000 21:33:16 -0500
"r.e.s." wrote:
> "Tom St Denis" <[EMAIL PROTECTED]> wrote ...
> [...]
> | Only lower case chars:
> | 1. Length of 7 chars, # of keys = 8,031,810,176 (2^33)
> | 2. Length of 14 chars, # of keys = 64,509,974,703,297,150,976
> (2^65)
> [...]
> | Lower+Upper
> | 1. Length of 7 chars, # of keys = 1,028,071,702,528 (2^40)
> | 2. Length of 14 chars, # of keys =
> 1,056,931,425,538,820,521,590,784
> | (2^80)
>
> Sorry to nitpick, but ...
>
> n 2^n
> ------------------------------
> 33 8589934592
> 40 1099511627776
> 65 36893488147419103232
> 80 1208925819614629174706176
>
> -r.e.s.
I would think there would be more collisions in the hash of shorter
passwords, are we assuming MD5 or SHA1?
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: What's better CAST in PGP or Blowfish 128bit?
Date: Sun, 03 Dec 2000 02:59:07 GMT
In article <90be2d$f2v$[EMAIL PROTECTED]>,
"Noname" <[EMAIL PROTECTED]> wrote:
> Hi all!
> What is better? CAST in PGP or Blowfish 128bit.
> Does anywhere exists freeware program with new and strong algorithm?
> Thx.
>
What is your requirement of the algorithms/systems?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Michael" <[EMAIL PROTECTED]>
Subject: Re: Newbie
Date: Sun, 03 Dec 2000 03:15:50 GMT
Thanks.
Michael
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:90c6tp$2th$[EMAIL PROTECTED]...
> In article <IrgW5.84992$[EMAIL PROTECTED]>,
> "Michael" <[EMAIL PROTECTED]> wrote:
> > Where do they post the algorithm for DES and RSA?
>
> RSA was formally documented in a paper written quite a while ago. I
> think the title was "A method of digital signatures" or something like
> that. If you go to www.counterpane.com/labs.html you should be able to
> look up the paper (Authors are R. Rivest, A. Shamir and L. Adleman).
>
> DES was designed by IBM in the 70's and is well documented in Bruce
> Schneier's Applied Crypto as well as quite a few websites.
>
> DES is not particularly "good" to look at from a beginners point of
> view, but structurally the cipher is rather simple.
>
> >
> > (you have peeked my interest in this area)
>
> I would then strongly recommend you buy some books in the area first.
> Instead of posting source code and "asking for analysis". Long time
> readers of this group will know that I started just like you did, but I
> learnt the most by trying to figure out for myself why things are not
> good. I am not the best cryptographer but I have a better intuition
> for "good designs" then I did a year ago. Often if you read the
> cryptanalysis papers you can figure out how the attack works and if it
> is applicable to new designs.
>
> Tom
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
------------------------------
From: "Michael" <[EMAIL PROTECTED]>
Subject: Re: Newbie
Date: Sun, 03 Dec 2000 03:24:37 GMT
Thanks.
It HAS been many years since I have taken a college level math class.
I still have all my books though. I have referred back to my statistics
book most often.
I am also trying to make my way through 'Applied Cryptography' as well. My
book was lost when I moved a year ago and I just went up into the attic and
found it a few minutes ago.
I will keep reading here and attempt to use my resources to make sense of
at least some of what I read here.
I find this a fascinating subject and it makes me wish I had more free time
to study it.
Thanks again.
Michael
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:90c7ok$7v0$[EMAIL PROTECTED]...
>
> Michael <[EMAIL PROTECTED]> wrote in message
> news:IrgW5.84992$[EMAIL PROTECTED]...
> > Where do they post the algorithm for DES and RSA?
>
> Well, for DES, a quick Web search pulled up:
>
> http://raphael.math.uic.edu/~jeremy/crypt/des.html
>
> which has a description of DES that doesn't look too bad (look under "How
to
> Implement the Data Encryption Standard").
>
>
> And, for RSA, I can describe it quickly:
>
> - At key generation time, you pick:
>
> p, q -- two distinct primes
> d, e -- two integers such that d*e = 1 mod lcm(p-1,q-1)
>
> - The public key (the key that you can give to all and sundry) is the pair
> (p*q, e)
>
> - The private key (the key that you must keep for your self) is the pair
> (p*q, d)
>
> - To encrypt the message P (or to verify a signature), anyone who has the
> public key can compute:
>
> C = P**e mod p*q
>
> - To decrpyt the message C (or to generate a signature), you (the one with
> the secret key) can compute:
>
> P = C**d mod p*q
>
>
> Notes:
>
> - If you are weak on number theory, this won't make much sense. Go study
it
> before trying to understand RSA (or any other public key cryptosystem, for
> that matter).
>
> - There are various considerations you need to make when you pick p, q, d,
> e -- just any old set may not be secure. For example, p and q must be
> chosen such that factoring p*q is infeasible.
>
> --
> poncho
>
>
>
>
>
------------------------------
From: "Michael" <[EMAIL PROTECTED]>
Subject: Re: Newbie
Date: Sun, 03 Dec 2000 03:30:11 GMT
And of course as comupters get faster, ya just make your key bigger to keep
ahead.
Michael
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Sat, 02 Dec 2000 05:27:33 GMT, "Michael" <[EMAIL PROTECTED]> wrote,
> in part:
>
> >I would think a (fast) computer would be perfect for brute forceing it.
> >But, I have no concept of just how fast the computers 'they' have are.
> >Mine is not up to the task!
>
> The idea is, though, that it's so trivially easy to use a bigger key,
> it shouldn't be too hard not to have to worry about what computers
> 'they' have. Unless they can do what Scotty couldn't, but the
> scriptwriters could and did every week: change the laws of physics.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
>
------------------------------
From: "Michael" <[EMAIL PROTECTED]>
Subject: Re: Newbie
Date: Sun, 03 Dec 2000 03:38:19 GMT
Wouldn't they have a large number of Cray T3Es?
All linked and working as one Mega computer.
Michael
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:90c7j2$3bi$[EMAIL PROTECTED]...
> In article <QhfW5.84973$[EMAIL PROTECTED]>,
> "Michael" <[EMAIL PROTECTED]> wrote:
> >
> > "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> > news:90au05$5ic$[EMAIL PROTECTED]...
> > > In article <9L%V5.84224$[EMAIL PROTECTED]>,
> > > "Michael" <[EMAIL PROTECTED]> wrote:
> > > > I would think a (fast) computer would be perfect for brute
> forceing
> > > it.
> > > > But, I have no concept of just how fast the computers 'they' have
> are.
> > > > Mine is not up to the task!
> > > >
> > > > I once (when I had a P200) wrote a program to attempt a brut force
> > > decode of
> > > > a simple message.
> > > > It was going so slow I added code to estimate (based on progress)
> how
> > > long
> > > > it would take to finish.
> > > > It was MANY YEARS! I gave up.
> > > > Not exactly practical.
> > > >
> > > > Thanks for the reply,
> > >
> > > Your concept of "fast computers" completely baffles me. A 500mhz
> > > Athlon computer (I think that is what you said you have) is capable
> of
> > > about 1.5 billion instructions per second (maximum) and would
> average
> > > about 500 million (assuming well written code, etc). Compare that
> to a
> > > 286 from 15 years ago... (286's ran at about 16mhz tops).
> > >
> > > Normally brute force is NOT the way to attack an algorithm. DES for
> > > example can be broken in theory by an attack faster then brute
> force.
> > > It just happens for short key algorithms such as DES it is more
> > > practical today to brute force the key.
> > >
> > > Often brute forcing is done on a cluster of computers (a DES key
> would
> > > takes months on a Atlhon 500) to linearly increase the search rate.
> > > distributed.net is a good example of such.
> > >
> > > Tom
> > >
> > >
> > > Sent via Deja.com http://www.deja.com/
> > > Before you buy.
> > >
> >
> > 1.5 Billion IPS. OK. What would you estimate the BEST the NSA can
> do on a
> > priority 1 job?
>
> The NSA is most likely the proud owner of several thousand 1ghz
> (probably upwards of 1GIPS) computers. I wouldn't say they have the
> enterprise computer though.
>
> For the most part brute forcing is not what the NSA would do anyways.
> More often then not poorly implemented (or home-brew crypto) crypto is
> the source of security leaks. If for example you have this magic
> crypto bubble and you use something like CAST with a 128-bit key then
> there would not be a chance in heck that you find the key before your
> great-great-great-great-great-great grandkids finish university.
> However, real applications exist outside the "magic crypto bubble" and
> are subject to often very unorthadox attacks (cramped RNGs for example).
>
> Currently distributed.net (a league of about 100,000 computers) has
> been clunking away on a 64-bit key for two years and is only 35% or so
> done. A 80-bit key is 65536 times harder and a 128-bit key is
> 18,446,744,073,709,551,616 times harder.
>
> Obviously brute force is not the means of attack the NSA (or
> any "cracker") would choose.
>
> Tom
>
> N.B the distinction between "cracker" and "hacker" is chosen. A hacker
> is someone who researches security related devices/applications to
> learn and hopefully help others. A cracker is someone with enough
> brains to double click on a program to perform malicous acts....
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
------------------------------
From: brian@@@wwwebweaver.com (Brian R. Bullock)
Subject: Re: The AES MixColumn transform
Date: Sun, 03 Dec 2000 03:43:34 GMT
My original post probably should have said "Anyone with an
explaination simple enough for a hobbyist thats trying to keep his
grey matter agile by learning something new". But the discussion on
"xtime" was exactly what I needed to help tie together the information
given in the Rijndael documentation.
I ran into one problem when inplementing the xtime function because
the language I'm using (Miva) is typeless so I couldn't define a 8-bit
word. I solved that by using a bit-wise AND 255 after shifting the
word one bit left.
So this is what I came up with:
Mr. Gladman's xtime function:
typedef unsigned char byte // must be 8 bits
byte xtime(byte x)
{
return (x << 1) ^ (x & 0x80 ? 0x1b : 0);
}
My xtime function:
<MvFUNCTION NAME = "xtime" PARAMETERS = "px">
<MvIF EXPRESSION = "{px BITAND 128}">
<MvFUNCTIONRETURN VALUE = "{((px BITSL 1) BITAND 255) BITXOR 27}">
<MvELSE>
<MvFUNCTIONRETURN VALUE = "{((px BITSL 1) BITAND 255) BITXOR 0}">
</MvIF>
</MvFUNCTION>
Where the instruction (px BITSL 1) means to shift the word contained
in the px variable one bit to the left, BITAND is a bit-wise AND, and
BITXOR is an exclusive bit-wise OR.
I agree that its much uglier than Mr. Gladman's function but testing
showed that it produces the same ordered sequence when fed the numbers
0 through 255. So I think its performing correctly.
Okay so I now have the tool necessary to find the product of each
vector in the state multiplied by the encryption matrix:
02 03 01 01
01 02 03 01
01 01 02 03
03 01 01 02
and the decryption matrix::
14 11 13 09
09 14 11 13
13 09 14 11
11 13 09 14
And if I understand this passage from the spec docs:
>2.1.3 Multiplication by x
<SNIP>
>x � b( x ) is obtained by reducing the above result modulo m( x ). If b7 = 0, this
>reduction is the
>identity operation, If b7 = 1, m( x ) must be subtracted (i.e., EXORed). It follows
>that
>multiplication by x (hexadecimal �02�) can be implemented at byte level as a left
>shift and a
>subsequent conditional bitwise EXOR with �1B�. This operation is denoted by b =
>xtime(a).
>In dedicated hardware, xtime takes only 4 EXORs. Multiplication by higher powers of x
>can
>be implemented by repeated application of xtime. By adding intermediate results,
>multiplication by any constant can be implemented.
>Example: �57� � �13� = �FE�
>�57� � �02� = xtime(57) = �AE�
>�57� � �04� = xtime(AE) = �47�
>�57� � �08� = xtime(47) = �8E�
>�57� � �10� = xtime(8E) = �07�
>�57� � �13� = �57� � (�01� XOR �02� XOR �10� ) = �57� XOR �AE� XOR �07� = �FE�
<SNIP>
( ed: the plus sign within a circle character was replaced by XOR in
the last line above.)
And since the language I'm using allows nested functions and the
functions will run before the XOR operation,
Then this:
�57� � �09� = 57 XOR xtime( xtime( xtime(57)))
And:
�57� � �11� = 57 XOR xtime( xtime( xtime( xtime(57))))
And:
�57� � �13� = ( 57 XOR xtime(57) ) XOR xtime( xtime( xtime(
xtime(57))))
And:
�57� � �14� = xtime( xtime(57)) XOR xtime( xtime( xtime(
xtime(57))))
Are what I need for the decryption matrix multiply
Is that correct?
Does the matrix multiply for the decryption follow the same sequence
as the one for encryption or does it need to be inverted in some way
(ie: start with byte 3 and work from right to left through the
matrix)?
Thanks to everyone that replied to my original post and thanks in
advance for any help with my current question.
Brian R. Bullock
------------------------------
** 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
******************************
