Cryptography-Digest Digest #425, Volume #13 Fri, 5 Jan 01 21:13:00 EST
Contents:
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: Key scheduling ("Joseph Ashwood")
HMAC-MD5 problems ("Bob Luking")
Re: Comparison of ECDLP vs. DLP (Roger Schlafly)
Re: HMAC-MD5 problems ("Joseph Ashwood")
Re: Padding ? (Rex Stewart)
Re: AES in optimized x86 assembler? (Helger Lipmaa)
xor'd text file ("Joshua Cryer")
finding unknown checksum / hash function ("Keith Monahan")
Re: HMAC-MD5 problems (Bryan Olson)
Re: NSA and Linux Security (Benjamin Goldberg)
Re: Differential Analysis (Benjamin Goldberg)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 05 Jan 2001 21:22:51 GMT
Subject: Re: Comparison of ECDLP vs. DLP
A few clarifications:
1) The table in ECCFUT paper also discusses DSA which is DLP. In fact the IFP
< DLP << ECDLP, for the known best method, but most people assume the IFP and
the DLP are essentially the same.
2) The numbers I give in ECCFUT are not MY numbers, they are from NIST and are
based on TIME. They were included in a DSA-2 draft which had longer key
lengths.
3) As pointed out in my paper, as symmetric keys, hashs and ECC all break based
on TIME, it is straightforward to compare them and compute equivalent keysizes.
The "problem" arises when you try to figure out an appropriate keysize for
RSA. If you use just TIME, you ignore the current storage costs. This has an
advantage in that algorithm space improvements and RAM technology improvements
do NOT affect your model, in that way it is consevative. Note that it is a
normal compsci process where space considerations are reduced by improved
algorithms, this happens time and time again.
If you shift to another model (like COST) then you have assumptions about
somehow translating TIME into SPACE through a COST function. How much do you
want to depend on this? Will RAM cost decrease faster or slower or the same
rate as CPU cost? You make your assumptions and you turn the crank.
So you can choose, depend on current TIME estimates or depend on current TIME
and SPACE estimates. The former is more conservative, the latter closer to
current reality, in some sense. But rememeber we are trying to extrapolate
into greater and greater levels of infeasibility and take a stab at the future
of what is known and what is possible.
Don Johnson
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Key scheduling
Date: Fri, 5 Jan 2001 13:46:45 -0800
> Somewhat off topic, but related is DES. Why didn't people redesign the
> DES key-shedule to deal with 128-bit keys (where complying to a
> standard was not essiential)?
Actually I believe it is highly related, because it can be easily used to
highlight another problem in this direction.
> 1. Design a new key-shedule to take 128-bit keys.
> 2. Increase the number of rounds to [be] 19 (this prevents Differential
> cryptanalysis from being possible according to AC2)
>
> If your gonna use tripple DES anyway, you probably wont care about the
> addition of 3 rounds to the cipher.
However you would in effect be changing the entire cipher, which would
remove all the validity of all (ok, most) prior analysis. There were in fact
efforts in this direction, however it was also found that even with
completey independent round keys DES could not be made much more resistant.
The addition of extra rounds would have been a good influence, this is
proven by observing that 3DES is basically DES with 3x the rounds. Would
this have been a good idea? Maybe. For some situations it may have been, and
may still be ideal. It's just that by making a complicated round key
function it may take significantly more time to get it right, look at the
AES competition, specifically at MARS, it started with key schedule A, a
flaw was found with it, but the round functions were still good, so they
switched to key schedule B, which according to some was actually *worse*
than schedule A. This wasn't the result of some crackpot that just wanted to
make a quick buck, this was from IBMs Crypto Research Lab a group that has
at least as much experience/genius/knowledge as any other such public group
in the world. So while it is fairly obvious that following the trend towards
strong key schedules is good, it does not come without it's own risks.
Joe
------------------------------
From: "Bob Luking" <[EMAIL PROTECTED]>
Subject: HMAC-MD5 problems
Date: Fri, 05 Jan 2001 22:42:54 GMT
I've encountered some problems running an HMAC-MD5 engine
I've built. My MD5 stream cipher algorithm is thoroughly tested
and working, but I' m not getting the proper digest out. I believe
that the packing order of my words into the inner engine is wrong.
I'm running the first test case in RFC 2202:
key = 0x0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
data = "Hi There"
digest = 0x9294727a3638bb1c13f48ef8158bfc9d
I'll append to the bottom of this post what I think is the proper
32bit word stream to be sent to the interior MD5 cipher block
(after padding and HMAC key insertion). If anyone can suggest
where I might have gone wrong, I would greatly appreciate it.
Thanks,
Bob
[EMAIL PROTECTED]
# 3d3d3d3d key ^ ipad
# 3d3d3d3d
# 3d3d3d3d
# 3d3d3d3d
# 36363636 ipad
# 36363636
# 36363636
# 36363636
# 36363636
# 36363636
# 36363636
# 36363636
# 36363636
# 36363636
# 36363636
# 36363636
# 54206948 "Hi There" (reverse order): T iH
# 65726568 : ereh
# 00000080 start of pad
# 00000000
# 00000000
# 00000000
# 00000000
# 00000000
# 00000000
# 00000000
# 00000000
# 00000000
# 00000000
# 00000000
# 00000240 start of message block length
# 00000000
result of inner hash = a71420c4f73e7966950243f898568cda
start again...
# 57575757 key ^ opad
# 57575757
# 57575757
# 57575757
# 5c5c5c5c opad
# 5c5c5c5c
# 5c5c5c5c
# 5c5c5c5c
# 5c5c5c5c
# 5c5c5c5c
# 5c5c5c5c
# 5c5c5c5c
# 5c5c5c5c
# 5c5c5c5c
# 5c5c5c5c
# 5c5c5c5c
# a71420c4 result of inner hash
# f73e7966
# 950243f8
# 98568cda
# 00000080 start of pad
# 00000000
# 00000000
# 00000000
# 00000000
# 00000000
# 00000000
# 00000000
# 00000000
# 00000000
# 00000280 start of message block length
# 00000000
result of outer hash = 38cb7a3990de034ab37782edda106742
(which is incorrect...)
Thanks for looking...
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Fri, 05 Jan 2001 14:51:24 -0800
Joseph Ashwood wrote:
> Given that you want this for a realistic comparison, I would recommend
> Silverman's numbers (http://www.rsalabs.com/bulletins/bulletin13.html
> section VIII), if you want to sell people on using ECC, Johnson's numbers
> (http://www.certicom.com/research/download/ECCFut.zip) do make a very good
> resource. The only problem is that these numbers compare RSA with ECC, and
> it seems you are interested in DLP, currently DLP and factoring are
> equivalent for the fastest method for both (it's the same algorithm).
This is a common misconception. Actually the best DLP method requires
a lot more RAM for phase-2 work, and that is critical for anything
bigger than about 512 bits. Eg, 512-bit RSA has been factored, but
no one knows how to crack 512-bit DLP with today's technology.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: HMAC-MD5 problems
Date: Fri, 5 Jan 2001 14:55:21 -0800
I think you're a bit confused.
> I've built. My MD5 stream cipher algorithm is thoroughly tested
This is the beginning of your biggest problems. MD5 is not a stream cipher
it as you said in the next line, a hash function. They are very different
entities.
> and working, but I' m not getting the proper digest out.
> MD5 cipher block
Here's a similar problem, MD5 is not a block cipher, it's a hash function.
Since you seem to be having problems with it, I'd recommend that you grab a
free version of the code (there are plenty), and make use of it. Alternately
you could have a look at RFC 1321 which details MD5 and is quite good at it.
Joe
------------------------------
From: Rex Stewart <[EMAIL PROTECTED]>
Subject: Re: Padding ?
Date: Fri, 05 Jan 2001 23:53:36 GMT
There was a discussion of data padding here from
5 Dec through 10 Dec about a similar subject.
Subj was "Wrapper Code" I also suggest a search
for the subject "Data Padding for Encryption"
to find out more about this subject. There are
references to RFC 1423 in those conversations,
and if memory serves that RFC references the ISO
or vice versa.
Sorry I can't be of more help.
--
Rex Stewart
PGP Print 9526288F3D0C292D 783D3AB640C2416A
In article <[EMAIL PROTECTED]>,
Mykhailo Lyubich <[EMAIL PROTECTED]> wrote:
> Hi,
>
> What is:
> "This algorithm uses outer CBC for triple DES.
> Input data is padded using the ISO
> 9797 method 1 scheme".
> (I know what the DES in CBC mode and padding are,
> but I have not any idea about "ISO 9797 method 1 scheme".)
>
> Regards
> --
> Mykhailo Lyubich
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: AES in optimized x86 assembler?
Date: Sat, 06 Jan 2001 02:08:13 -0500
Paul Crowley wrote:
> Off hand, I can think of no better candidate for assembly hacking than
> AES on the x86.
>
> * Crypto routines are great candidates for assembly implementation:
> they're small, they perform an extremely well defined function with a
> simple interface, and under some circumstances they're an application
> bottleneck.
true
>
> * x86 is not a compiler-friendly IA, so hand-hacked assembly by an
> expert still does considerably better than compiler-generated code.
> Especially if your compiler is GCC; x86 optimisation is not GCC's strong
> suit. See http://www.goof.com/pcg/
true. my highly optimized assembly version of Rijndael for P3 is 1.5 times
faster than (almost as) highly optimized C version (under a late snapshot
of gcc)
> * I for one hope to see AES universally adopted as the default crypto
> algorithm. x86 is the most widely-used IA inthe world. It could be one
> of the most popular bits of assembly ever.
>
> Admittedly, Rijndael is a very compiler-friendly algorithm, so it might
> benefit from assembly coding less than most tight loops. Nevertheless,
> I'm very surprised that several blazing x86-asm implementations of this
> algorithm aren't already duelling for speed supremacy; the only such
> implementation listed on http://www.rijndael.com/implementations.html
> uses only 8086 instructions and is optimized for size, not speed.
>
> Come on, you x86 speed demons, here's a challenge worth leaping to! How
> much better than gcc -O3 can you do?
Many implementations haven't mentioned there. Check out also
http://www.tml.hut.fi/~helger/aes.
Helger
http://www.tml.hut.fi/~helger
------------------------------
From: "Joshua Cryer" <[EMAIL PROTECTED]>
Subject: xor'd text file
Date: Fri, 5 Jan 2001 16:37:37 -0800
Hey, I got a pretty large text file that has been encrypted using a very
simple xor algorithm. The only thing I am sure of is that the seed is no
larger than 65535. I don't know how many times it was encrypted. Could
someone help me out a bit here? (i.e. a paper on cracking xor encryption.)
Thanks in advance.
------------------------------
From: "Keith Monahan" <[EMAIL PROTECTED]>
Subject: finding unknown checksum / hash function
Date: Sat, 06 Jan 2001 01:18:17 GMT
First, can anyone make a clear distinction between a checksum and a hash? I
find a lot of their properties overlap. Both checksums and hash functions
typically accept some arbitrary-length message(whether or not they are
broken into parts prior to processing) and produce a fixed length output. I
figure things like hard to reverse, and a collision resistance is more a
design criteria for a hash than for a checksum.
In any event, I'm faced with solving a problem. I'm trying to figure out a
checksum function, which takes approximately 524 +/- bytes as input, and
outputs a 32-bit checksum. The function is completely unknown, at least to
me, and I'm trying to figure out how reproduce the function. I need to
figure out what operations to perform on the input to give me the correct
output.
I can't control the input to the function but I do have some sample
input->output pairs.
My guess is that the checksum function was really designed for a data
integrity check and not done as any security measure. So what this means,
is that this probably isn't a secure hash, and I doubt anything like MD5 or
SHA1 was used. Not to mention, the output of the function is only 32-bits
and obviously no one would design a secure hash function whose output is
that small. I suppose they could have used MD5 and chopped off the least
significant bits --- but I doubt they went through that much trouble for a
checksum function.
Can anyone provide me with details on how to proceed? I would appreciate it
and I have all the standard texts available (AC, HAC, Dr Dobbs collection,
etc) so feel free to reference.
Thanks,
Keith M
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: HMAC-MD5 problems
Date: Sat, 06 Jan 2001 01:53:24 GMT
Bob Luking wrote:
> I've encountered some problems running an HMAC-MD5 engine
> I've built. My MD5 stream cipher algorithm is thoroughly tested
> and working, but I' m not getting the proper digest out. I believe
> that the packing order of my words into the inner engine is wrong.
If your MD5 hash really is working, you can ignore the packing
order when building HMAC from it. See what you get when you
MD5-hash the byte sequence (given in hex):
3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d
36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36
36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36
36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36
48 69 20 54 68 65 72 65
The correct answer is:
90 1d 23 73 2e dc c0 f1 a1 06 53 2f 6b e5 ec eb
Those are the inputs and outputs for the "inner hash" in the
given example. If that's not what you get, then your MD5 is
bad. If that is what you get, then the problem is in your
construction of the pre-image.
Below is Python code for simple, single-call HMAC-MD5,
HMAC-SHA-1, and generic HMAC. Both SHA-1 and MD5 are standard
Python libraries.
--Bryan
|
| import sha
| import md5
| import string
|
|
| def xor_strings(s1, s2):
| """Pass two strings of the same length; returns their
| bit-wise exclusive or.
| """
| char_list = map(lambda x, y: chr(ord(x) ^ ord(y)), s1, s2)
| return string.join(char_list, "")
|
| def hmac(message, key, hash_function, block_size):
| """Generic HMAC, as per RFC 2104. The hash function must
| follow the usual Python new..update..digest interface.
| """
| if len(key) > block_size:
| key = hash_function.new(key).digest()
| ipad = chr(0x36) * block_size
| opad = chr(0x5C) * block_size
| key = key + chr(0) * (block_size - len(key))
| hash1 = hash_function.new(xor_strings(key, ipad))
| hash1.update(message)
| hash2 = hash_function.new(xor_strings(key, opad))
| hash2.update(hash1.digest())
| return hash2.digest()
|
| def hmac_sha1(message, key):
| return hmac(message, key, sha, 64)
|
| def hmac_md5(message, key):
| return hmac(message, key, md5, 64)
|
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Sat, 06 Jan 2001 02:01:47 GMT
John E. Gwyn wrote:
>
> Stephan Eisvogel wrote:
> > 4. Selinux is the best attempt so far to rid Un*x-like systems from
> > the big drawback of having almighty powers as 'root'. There are
> > other approaches like LIDS, sudo or the evil suid-bits, but they
> > all do not separate policy from enforcement (i.e. once God, laws no
> > longer apply to you).
>
> No, actually there have been quite a few UNIX-derived systems that
> do not have such a property. Plan 9 from Bell Labs is pretty good
> on that score; in its intended configuration services are assembled
> on a per-"user" basis with every request being vetted by an
> authentication server, all the way down to the low-level protocols.
Maybe, but Plan 9 is, well, bizarre. Not that it doesn't have a number
of interesting/useful features, but the way you can "mount" a directory
over another, forming a sort of union of the two directories, is quite
strange, imho, and the fact that it doesn't have anything resembling
symbolic links (aka shortcuts for you win and mac folks) is quite
annoying.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Sat, 06 Jan 2001 02:01:49 GMT
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
[snip]
> > How about this: here's what I want to analyse:
> >
> > function encr( uint8 txt[2], uint8 k[rounds] ) {
> > for i in 0 to rounds/2-1 {
> > txt[0] ^= AES_sbox[ txt[1] ^ *k++ ];
> > txt[1] ^= AES_sbox[ txt[0] ^ *k++ ];
> > }
> > }
> >
> > How do I go about finding differences and probabilities, and how
> > does that let me get k? Of equal importance, what do I have to set
> > rounds to to thwart differential analysis?
>
> Well look at the xor-pair table of the sbox and see if any high prob
> difference can propagate easily in your function. (Hint your above
> function is a simple feistel so just look for high probability output
> differences that have inputs of high prob as well (i.e if you chain
> the differences they are always high probability)).
>
> Tom
In the AES sbox, there are 23 diferentials which have a probability of
6/256. There are a large number of differentials with probability of
4/256, 2/256, and 0.
The only differentials that seem to chain, at all, remaining at a
slightly high probability are:
0x4d->0x80->0xa6
0x68->0x26->0x94
Assuming that my understanding of differential analysis is right, this
means that with probability 36/65536, an input difference of 004d
becomes an output difference of 80a6 after two rounds, or an input
difference of 0068 becomes an output difference of 2694 after two
rounds. There does not seem to be any chain of high probability
differentials which holds for more than 2 rounds.
With 4 rounds, getting key bytes with differential analysis should be
impossible, or close to it.
For an sbox with an even lower max DP (such as the one in Tom Denis's
TC5), a differential attack on a 16 bit fiestel using it is, umm, even
more impossible.
It would thus seem to me, that hypercrypt with IROUNDS set to 4, and
OROUNDS reduced to 1, is not attackable with differential analysis.
Does anyone care to contradict me?
Since Richard Heathfield was so kind as to provide me some web space,
you can find hypercrypt online at
http://users.powernet.co.uk/eton/guest/beng/hypercrypt.txt
I plan on sending Richard a new version soon, with some minor changes...
though most of them are to the description of it's good and bad points.
If OROUNDS is set to 1 or 2, and IROUNDS to 4, hypercrypt should be both
secure and fast, even on an 8-bit architecture. (I think. Anyone want
to give me timings of it, and a comparison to, say AES?)
Incedentially, although I don't see any logical, mathematical, reason to
set OROUNDS to a number greater than 1, neither do I get any kind of
warm fuzzy feeling from only one outer round, and thus plan on having
OROUNDS set to 2.
Can anyone give me some advice either way? I feel a bit silly making my
decision based on a warm fuzzy feeling [or lack thereof].
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
** 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
******************************
