Cryptography-Digest Digest #426, Volume #13 Sat, 6 Jan 01 03:13:01 EST
Contents:
Re: finding unknown checksum / hash function ("Matt Timmermans")
Re: Genomes (Terry Ritter)
Re: Differential Analysis (Tom St Denis)
Re: finding unknown checksum / hash function ("Keith Monahan")
Re: finding unknown checksum / hash function ("Matt Timmermans")
Standard steganography (was Simple Subliminal Exercise) (David Hopwood)
Re: HMAC-MD5 problems (David Hopwood)
Re: Comparison of ECDLP vs. DLP (David Hopwood)
Re: Input/Ouput-conversion for DES password encryption ("Wouter")
Re: finding unknown checksum / hash function (Paul Rubin)
----------------------------------------------------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: finding unknown checksum / hash function
Date: Sat, 06 Jan 2001 02:09:14 GMT
"Keith Monahan" <[EMAIL PROTECTED]> wrote in message
news:tnu56.282$[EMAIL PROTECTED]...
> First, can anyone make a clear distinction between a checksum and a hash?
I
> find a lot of their properties overlap.
They are designed for different purposes:
A checksum is designed to catch errors in the original message -- whatever
errors the designer considers to be most likely. For typical message sizes,
for example, a CRC will catch all errors that are limited to a few bits, and
all errors that occur in a "burst" that is smaller than the size of the CRC.
A checksum is usually transmitted with the message, and so it will typically
need to catch similar errors in the checksum as well. The name "checksum"
comes from the original and not very effective method of adding up all the
digits or characters in the message. These days, they are more commonly
refered to as error detection codes.
A traditional hash function is designed to produces a uniform distribution
of output values from different inputs. Hash functions are used to
implement many randomized algorithms and data structures (like hash tables).
Cryptographic hashes are different. They needs to be hard to reverse, i.e.,
they need to be very good error detection codes that can detect any errors
introduced by malicious and intelligent attackers who are trying to fool the
hash. They typically need to be collision resistant. Sometimes they _need_
to be good traditional hashes as well, but its always a good idea, because a
cryptographic hash that doesn't produce evenly distributed outputs for
typical inputs is inefficient.
> 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.
The first thing to try is to flip a bit in the input and see the difference
it makes in the checksum (XOR). Then fix the file and flip a bit that's 32
bits away. If the difference is the same, then it's likely that you have
either a CRC or a simple checksum. If the difference is only a bit, then
it'll be a simple checksum. Otherwise, see if the difference corresponds to
any of the standard CRC polynomials.
> I can't control the input to the function but I do have some sample
> input->output pairs.
Ok, so you can't do the above... The next best bet is to try some of the
standard checksum algorithms -- grab CRC and Adler32 from zlib or some other
source -- it's likely to be one of these.
> My guess is that the checksum function was really designed for a data
> integrity check and not done as any security measure.
That is correct -- if it was a security measure, it would be longer than 32
bits, unless these messages are actually serial numbers.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Genomes
Date: Sat, 06 Jan 2001 03:06:00 GMT
On 5 Jan 2001 18:54:46 GMT, in
<01c0774a$05965f40$[EMAIL PROTECTED]>, in sci.crypt
"John Feth" <[EMAIL PROTECTED]> wrote:
>I looked at about 700,000 bases (base here relates to a chemical
>constitution of the components A, C, G, T, not numerical) on a gene and
>found the A:C:G:T ratios to be very close to 3:2:2:3. An Allan deviation
>analysis shows that the order looks like noise in strings of up to about
>1,000 bases but carries information in strings from 1,000 to 10,000 bases
>long. I believe an A always occurs with a T so steganography in DNA might
>be a little different than in photos or music.
Although I am somewhat familiar with "Allan variance," and continue to
read the many papers available on the web, I am confused about the
implication that it can be relied upon to distinguish between noise
and information. Perhaps you would care to describe your experiments
in detail.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Sat, 06 Jan 2001 03:01:18 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> 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.
Wrong. The highest xor-pair probability is 4/256 not 6/256.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Keith Monahan" <[EMAIL PROTECTED]>
Subject: Re: finding unknown checksum / hash function
Date: Sat, 06 Jan 2001 04:36:23 GMT
Matt,
Thanks for the response.
| The first thing to try is to flip a bit in the input and see the
difference
| it makes in the checksum (XOR). Then fix the file and flip a bit that's
32
| bits away. If the difference is the same, then it's likely that you have
| either a CRC or a simple checksum. If the difference is only a bit, then
| it'll be a simple checksum. Otherwise, see if the difference corresponds
to
| any of the standard CRC polynomials.
Ok that makes a lot of sense. Where can I find a list of the "standard CRC
polynomials" ?? Of course it won't work in my case anyways because I can't
modify the input but would be nice for future reference.
| Ok, so you can't do the above... The next best bet is to try some of the
| standard checksum algorithms -- grab CRC and Adler32 from zlib or some
other
| source -- it's likely to be one of these.
Great. I'll give those a try soon.
| That is correct -- if it was a security measure, it would be longer than
32
| bits, unless these messages are actually serial numbers.
I suspected someone might think that, but most of the regulars here will at
least recognize my name as someone who is truly interested in the subject
from a mental challenge perspective. Besides, you can typically control the
input to shareware software where the key/serial/etc is based on a
username/company name/etc. In addition, even the dumb shareware authors are
using longer hashes than 4 bytes! :)
In reality, I'm working on a flash card that contains some data on it. The
flash card uses what are called bad block tables which basically tell the
system which pages on the flash card are valid and which ones are not.
Since the system refuses to load pages whose page number is in the bad block
table, the table must be modified. The table has a checksum to make sure
the table is not corrupt --- and this checksum is at the end of each page of
the table, which happens to be around 528 bytes long. It actually gets more
complicated than this -- and this is the easy part.
With that being said, this project is slightly more interesting than ripping
$19 off some kid who spent 90,000 hours working on his first visual c++
project.
Thanks again for your comments and your reply,
Keith M
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: finding unknown checksum / hash function
Date: Sat, 06 Jan 2001 07:17:12 GMT
"Keith Monahan" <[EMAIL PROTECTED]> wrote in message
news:bhx56.129$[EMAIL PROTECTED]...
> Ok that makes a lot of sense. Where can I find a list of the "standard
CRC
> polynomials" ?? Of course it won't work in my case anyways because I
can't
> modify the input but would be nice for future reference.
Good question. There's this one:
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 +
x^4 + x^2 + x^1 + x^0
This is the one used in CCITT-32 CRC, Ethernet, FDDI, and PKZip. Either
this one, or its reverse, is the most likely. Others you can find by
examining source that does CRC's. You won't find too many, because people
don't typically make up new ones.
> | That is correct -- if it was a security measure, it would be longer than
> 32
> | bits, unless these messages are actually serial numbers.
>
> I suspected someone might think that, but most of the regulars here will
at
> least recognize my name as someone who is truly interested in the subject
> from a mental challenge perspective.
I didn't mean it that way -- serial numbers often use 32-bit hashes for
security, because they have to be typed in manually.
> In reality, I'm working on a flash card that contains some data on it.
If it's a flash card, then the hash is almost certainly a CRC, and probably
using the polynomial above.
------------------------------
Date: Sat, 06 Jan 2001 01:34:06 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Standard steganography (was Simple Subliminal Exercise)
=====BEGIN PGP SIGNED MESSAGE=====
Anonymous Remailer wrote:
> Steganography is a question of familiarity, that's why it is
> pointless to have "standard stego".
There are some applications for which "standard stego" makes sense. For
example, suppose that a steganographic filesystem were bundled with an
operating system, and enabled by default (this need not result in an
excessive performance penalty). If there were other reasons to use that
OS, then it wouldn't be possible to conclude much simply from the fact
that the steganographic FS was present. Without the passwords for any
hidden levels (which may or may not exist), it would not be possible
to tell whether any extra data had been stored - short of torturing the
user, possibly.
- --
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
iQEVAwUBOlZ10TkCAxeYt5gVAQHvSggAhWVrBVMKyO1lPyAbP7H/VtiIigff9GIz
z6Idkvftwq8kGjTWeRpEz8/cDzSaIMaHW64d0YPCdVXucUbEakGMref0Cyqc9RDc
SNSSRx4S6k2QOjH/ht532NC1OrBK2rdORuiWxQCUr2dk+2geUixXOXonKphwobdK
d3CE6pilwUuaywc0bJZ9VAGBKGmqimE+IemkW3B72aXRHRy1S5z9Mp+amz+Q2HvP
3bUwaMLjiEYMqSMX5Z+PKqwZnI+f0AgHhLAUcKloLdvWd3LSnqLe3W0thNpN7E+A
dF/4aUFSyw7Ule2hE95mtburzc9m02TIM4EXYYW8LJOzxBMCoD9AVA==
=/ztn
=====END PGP SIGNATURE=====
------------------------------
Date: Sat, 06 Jan 2001 03:28:54 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: HMAC-MD5 problems
=====BEGIN PGP SIGNED MESSAGE=====
Bob Luking wrote:
> I've encountered some problems running an HMAC-MD5 engine
> I've built.
[snip]
> result of inner hash = a71420c4f73e7966950243f898568cda
>
> start again...
[snip]
> # a71420c4 result of inner hash
> # f73e7966
This is the wrong byte order, I think (assuming you printed the
inner hash in little-endian order). Try c42014a7 66793ef7...
- --
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
iQEVAwUBOlaQTzkCAxeYt5gVAQHplwf8DWKR/WOpDOJ2v4uPvRJx/CBzkUpyBcSD
CQQOFBbvMFtebSkfSPOA5XgJq+taesDYS5JPtlozMnwjrnrJRUWxD6o1PSH4G1g8
kb8ElUgyU/jzufDC/VRfK6GKDaKQyyhMmXIOJs7DZffOpwBasdOI9Dvwd4FcR5TU
aaD07x5NR1Z4cOdWzukWPo70bF88r6iMVmhOQsy54mxiB2PHRDe8FXaZhEFxMpM2
4agcos77AbIzPu5PdKIFMN9pNvRYU5RyukNerRBZMyClAZKRbCbv9xqYYuJU0PAM
eVSTk9yA5mF1PVSPQs3IF3EK3rPxa0QRvpuOJF7nzEE9GyBq2eXFjA==
=7am0
=====END PGP SIGNATURE=====
------------------------------
Date: Sat, 06 Jan 2001 05:15:07 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Comparison of ECDLP vs. DLP
=====BEGIN PGP SIGNED MESSAGE=====
Martin Hamann wrote:
> I'm looking for at comparison of the stregths in a Elliptic Curve DLP and
> a DLP in Zp*. I have seen a table stating which keysizes roughly offer the
> same strength, for example 2^106 in ECDLP roughly equals 2^512 in "normal"
> DLP. I believe it is taken directly from a book or article, which I cannot
> locate.
>
> I need it for a discussion of why ECDSA is 'better' than DSA.
It isn't. To answer the question you probably meant to ask:
ECDSA DSA
+ - Known attacks against ECDSA (with well-chosen parameters) are
exponential in the group order, as opposed to subexponential
for DSA.
+ - EC public key sizes are smaller for a given conjectured level
of security.
+ - ECDSA can be faster than DSA for a given conjectured level of
security, *if* it is well-optimised.
- There is an attack by Serge Vaudenay that reduces the cost of
finding collisions for DSA to less than the expected 2^80
operations (when used with SHA-1); this attack does not
apply to ECDSA as standardised, but it is not particularly
serious in any case.
- + Well-optimised implementations of ECDSA, in either hardware
or software, are less common, and tend to only implement
a subset of options (see next point).
- + Ensuring interoperability is significantly harder for ECDSA
because there are several field and basis options.
- + EC systems are more complicated to implement, and therefore
there is a greater chance of an implementation bug affecting
security.
- + Some methods of implementing field arithmetic used in EC systems
are patented. Also the patent status of point compression
(for an ECDSA public key, for example) is uncertain. DSA is
technically patented by the US Government, but with a
royalty-free open license.
- + Generation of parameters for EC cryptosystems is *much* more
complicated (although it is possible to use parameters that
were generated by someone else). Generation of DSA parameters
is quite easy.
- + The EC discrete log problem is arguably less well understood
or thoroughly analysed than the DLP in a subgroup of GF(p).
- + There is a greater risk of choosing classes of EC parameters
that turn out to be weak - c.f. Smart's attack on EC(GF(2^m))
with m composite. (This is especially true if you choose
parameters to enable specific optimisations, so be careful
of performance analyses that do this.)
+ + There is an advantage to supporting both ECDSA and DSA in case
an attack is found on one of them (although not if you design
a system so that a break in either will break the system).
= = Signature sizes are identical. Message recovery is not
supported.
= = Both are believed to provide existential unforgeability under
chosen message attack (but see the next point).
- - Neither DSA nor ECDSA are supported by security proofs
(unlike, say, RSA-PSS or RW-PSS).
Overall I think the above arguments favour DSA for most typical
applications (or one of RSA-PSS or RW-PSS if you don't restrict the
choice to DSA and ECDSA), but YMMV.
Also, remember that the vast majority of feasible attacks against
cryptographic systems are not cryptanalytic attacks against algorithms.
- --
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
iQEVAwUBOlapMDkCAxeYt5gVAQGxhgf/d2Q8U80l3975V8+YrcvgzGLnYIlMoGDp
sNICr+REUj9NgGze5xg4sTGl1Q157dWLGDgbs1U/yxFWuQaJJc6rDNIVm1GzQNf4
fQEdVW0zfhjQZfDZfFxIaxPxooXGQi+K/vcOszaP1s+zlg81HuCALZlaGY9vN/FV
8+1JmNYMf2gKwPHv0S0f4jEeEvpGyP2g1bdEeIz8sMy2660VyapDjmUySasy1qAS
BWvA3ePZMcUOi6yaCQMIMycVtStuUhWJla3XfaXAcjEhxP4hapxg0kLl1JNx7M0e
I1FVt7uM+tjc1ozPaOIgdRaHormDNzzT/Xsnoxxgw9Ydo/76KD2FEQ==
=SewD
=====END PGP SIGNATURE=====
------------------------------
From: "Wouter" <[EMAIL PROTECTED]>
Subject: Re: Input/Ouput-conversion for DES password encryption
Date: Sat, 6 Jan 2001 08:54:04 +0100
[EMAIL PROTECTED] wrote in message <9309se$u00$[EMAIL PROTECTED]>...
>In article <930639$i88$[EMAIL PROTECTED]>,
> "Wouter" <[EMAIL PROTECTED]> wrote:
>> Hi,
>>
>> I am working on a encryption program (just for fun) which encodes
>password
>> using DES. I have written the entire algorithm, and probably
>the 'main'
>....
>
>> I hope someone can help me. Any hints or code (basic / C / pseudo-
>code) will
>> be very much appreciated. I haven't found any information about this
>parts
>> of the algorithm on the internet.
>>
>> Wouter
>>
>
>What you describe looks like the Unix crypt3 system call. This is not
>the official DES but a special implementation of it. You can find
>source code to do the password conversion here:
>http://www.cs.ucsb.edu/~mdipper/crypt/crypt3.c
>
Thanks. The code you referred to has helped me much.
I had the bits of the salt swapped. My algorithm is working fine now.
Wouter
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: finding unknown checksum / hash function
Date: 06 Jan 2001 00:06:37 -0800
"Keith Monahan" <[EMAIL PROTECTED]> writes:
> Ok that makes a lot of sense. Where can I find a list of the "standard CRC
> polynomials" ?? Of course it won't work in my case anyways because I can't
> modify the input but would be nice for future reference.
Before doing that, it's easiest to just take two pairs of messages
(A1,A2) and (B1,B2) where A1 and A2 differ by just one bit (say bit 63),
and B1 and B2 differ by the same bit. Then if (hash(A1) xor hash(A2))
is the same as (hash(B1) xor hash(B2)), you're probably looking at a CRC.
> The table has a checksum to make sure the table is not
> corrupt --- and this checksum is at the end of each page of the
> table, which happens to be around 528 bytes long. It actually gets
> more complicated than this -- and this is the easy part.
If the checksum is computed by the flash controller, it's almost
certainly something very simple, like an arithmetic sum.
------------------------------
** 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
******************************
