Cryptography-Digest Digest #240, Volume #13 Wed, 29 Nov 00 12:13:00 EST
Contents:
Re: Role of linguistics (Mok-Kong Shen)
Re: collision probability with file checksums (David Schwartz)
Re: collision probability with file checksums (David Schwartz)
Re: DES question: Has this ever been proven before? (Francois Grieu)
Re: Rijndael applications ([EMAIL PROTECTED])
Re: PDF/PS to MS WORD converter ([EMAIL PROTECTED])
Re: Blowfish key input size (Tom St Denis)
Re: On mutation of crypto algorithms (Tom St Denis)
Re: Rijndael applications (Sami J. M�kinen)
Re: Isomorphic Elliptic Curves (Robert Harley)
Re: collision probability with file checksums (Ed L Cashin)
keysize for equivalent security for symmetric and asymmetric keys
([EMAIL PROTECTED])
Re: keysize for equivalent security for symmetric and asymmetric keys (JCA)
Re: keysize for equivalent security for symmetric and asymmetric keys (DJohn37050)
Re: collision probability with file checksums (John Myre)
Re: collision probability with file checksums (DJohn37050)
Re: Public key encryption in Javascript? ([EMAIL PROTECTED])
Re: collision probability with file checksums (David Wagner)
Re: DES question: Has this ever been proven before? (David Wagner)
Re: keysize for equivalent security for symmetric and asymmetric keys (DJohn37050)
Re: DES question: Has this ever been proven before? (David Wagner)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Role of linguistics
Date: Wed, 29 Nov 2000 11:56:52 +0100
Joseph Ashwood wrote:
>
> It is of less interest now, that much is true. But the ability to recognise
> a language (i.e. recognise possible plaintext) is still very important. So
> the role is still non-trivial, but it is becoming less worthwhile.In some
> cases like RSA, knowledge of the encrypted language is currently fairly
> worthless because the best attacks on it (factoring) do not depend on any
> internal knowledge. However in many cases this is simply not true, and
> breaking Rijndael will almost certainly require having at least some basic
> knowledge of the formatting/language of the underlying data.
>
> In some extreme cases having the extra knowledge of the language is even
> more useful. At a previous employer they used RC4 to encrypt a data stream.
> I proved the folly of doing that with their formatting by handing my boss
> his password (it was in Russian, a language I can't even recognise all the
> letters from), something he did not appreciate being possible. This was a
> protocol failure which managed to show through the RC4 stream. A while ago
> on this group I proved myself wrong in very much the same way, by creating a
> protocol where knowledge of the language would clearly show through even the
> strongest encryption. What I did is I defined a perfect block cipher on an
> n-bit block, then I took the plaintext (any plaintext it didn't matter which
> one), and padded using 0s such that each block had one and only one bit of
> plaintext, and the plaintext was in the same location in each block (e.g.
> 3DES and padding each plaintext bit with 63-bits of 0). After encryption the
> stream can be compressed to the original stream (or it's logical inverse),
> making the encryption completely worthless. In these cases knowledge of the
> language being used allows the attacker to avoid attacking the underlying
> cipher.
I think that your example also offers an understandable
hint (though a weak one because the example is extreme)
that preprocessing with either compression or a simple
processing step could provide some non-trivial value.
M. K. Shen
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: collision probability with file checksums
Date: Wed, 29 Nov 2000 02:52:35 -0800
Bryan Olson wrote:
> The application here is a Tripwire-like system, which does
> not correspond well to either PK signatures or MAC's. The
> goal of the system is to detect and report changes in a set
> of files. Tripwire is useful (perhaps most useful) against
> insider attacks, and an author of one of the files is a
> potential attacker.
The difficulty of this type of attack is extreme. Consider the two
payloads, the innocent one and the harmful one. Assume that the intruder
has created a 'space' inside both payloads that he can put anything in
without affecting the efficacy of either payload. He needs to find a
padding value for both payloads such that their hash is the same. This
is even harder than finding a single collision, precisely equivalent to
finding a collision for a specified file.
In other words, that the intruder is an insider able to pick the
initial file contents, does not simplify his attack in any way. The
search for an initial file with the same hash as a malicious file is
precisely as hard as the search for a malicious file with the same hash
as an initial file.
DS
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: collision probability with file checksums
Date: Wed, 29 Nov 2000 02:53:46 -0800
David Schwartz wrote:
> In other words, that the intruder is an insider able to pick the
> initial file contents, does not simplify his attack in any way. The
> search for an initial file with the same hash as a malicious file is
> precisely as hard as the search for a malicious file with the same hash
> as an initial file.
Five seconds after posting this, I realized that I'm totally wrong.
*sigh*
DS
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: DES question: Has this ever been proven before?
Date: Wed, 29 Nov 2000 12:08:02 +0100
David Wagner wrote:
> Francois Grieu wrote:
>> Yes, Knuth's TAOCP present this algorithm. But there is no reason that
>> an ENTRY in the cycle, which is what we are looking after, is for some
>> n with a(n) = a(2n) so IMHO the technique does not apply.
>
> I think it does apply.
I respectfully challenge your point of view.
> Once you find n so that a(n) = a(2n), you know the period of the cycle
Yes, I see how to determine the length of the cycle: it is easy enough
to get it by stepping forward from a(n) and reaching it again [beside,
since this period is a divisor of n, one need not step all the way
through, it is enough to make n/p steps with p the smallest prime factor
of n, and if the period is not yet found it must be n]
> and you can deduce the length of the "leader" which enters the cycle
I fail to see how. I see that the length of the "leader" is at most n.
But we would need the exact length of the leader to pinpoint the
collision, right ?
> hence you can walk forward again from the starting point to find the
> collision.
How can we detect the collision point, except with a collision search
method using some memory [or an O(n^2) algorithm], that it seems would
have been best used from the beginning ?
Granted, if the cycle turns to be small, we can put only the cycle (or a
distinguished portion thereof) in memory, and save the memory for
the "leader" part; but still the preliminary cycle finding does not seem
very useful compared to cycle-finding with distinguished points.
Francois Grieu
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Rijndael applications
Date: Wed, 29 Nov 2000 11:49:41 GMT
On Tue, 28 Nov 2000 22:50:32 GMT, "Red Shadow"
<[EMAIL PROTECTED]> wrote:
>I'm a student of the university in Ghent and I'm writing a presenation on
>Rijndael. I'm looking for some application or some systeem who are already
>using this algoritme.
>Thanx
>Lieven
>
www.privatecrypt.com
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: PDF/PS to MS WORD converter
Date: Wed, 29 Nov 2000 12:17:30 GMT
On Tue, 28 Nov 2000 01:48:03 GMT, Raphael Phan <[EMAIL PROTECTED]>
wrote:
>Hi,
>
>Anyone know of any PDF or PS to MS Word converter? I know of some that
>facilitate the other way round but not PDF to Word...
>
>Raphael
>
No, but a combination of Aladdin Ghostscript, Ghostgum's GSview and
pstotext will extract the text from PDF or PS. pstotext was written by
Andrew Birrell and Paul McJones. It is Copyright (C) 1995-1996,
Digital Equipment Corporation.
GSview (gsv34w32.exe) can be got from
http://www.cs.wisc.edu/~ghost/gsview/get34.html
Aladdin Ghostscript 6.01 (gs601w32.exe) can be got from
http://www.cs.wisc.edu/~ghost/aladdin/get601.html
pstotext is included in the GSview zip archive.
You will have problems if the files you are looking to convert from ps
or pdf use specialised fonts (eg math symbols) as pstotext renders the
text in the ISO-Latin1 character set.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Blowfish key input size
Date: Wed, 29 Nov 2000 12:37:03 GMT
In article <902m5i$j6l$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi Custerstoe,
>
> In article <900rla$3q7$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
wrote:
> >> I can't sleep thinking about why it is said that the input key of
> >> Blowfish (16 rounds) is up to 56 bytes. It seems that the limit is
in
> >> 72 bytes (16 + 2) * 4...
> >> Please let me sleep again, thanks.
> > I don't know if this will be your sleeping pill but the document:
> > http://www.counterpane.com/bfsverlag.html says:
> > "The 448 limit on the key size ensures that the every bit of every
> > subkey depends on every bit of the key. (Note that every bit of P15,
> > P16, P17, and P18 does not affect every bit of the ciphertext, and
> > that any S-box entry only has a .06 probability of affecting any
> > single ciphertext block.)"
>
> Thanks for your input. I had noticed that, but wouldn't give a key
> greater than 448 bits more security than just 448? It would be less
> than its effective size, but better anyway...
Does it really matter? A 448-bit key is already excessively large.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: On mutation of crypto algorithms
Date: Wed, 29 Nov 2000 12:36:20 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
>
> [snip]
> > In the case of AES (Rijndael) it is quite easy to permute the sbox
and
> > not change any of it's current DP/LP maximums. Just multiply in GF
> > (2^8) the input polynomial then add a displacement polynomial...
> >
> > i.e
> >
> > Sbox'(x) = Sbox(a.x + b)
> >
> > You can now make "(255)(256) - 1" new copies of Rijndael which are
all
> > equally secure.
>
> Maybe S''(x) = c*S'(x) + d would also work.
>
> It is my position as expressed in the original post that,
> since Rijndael has been extremely successful in providing
> a very simple and strong design, we could easily allow
> ourselves the luxury of introducing a little complexity
> in applications where standard conformity is not an issue.
> That opportunity is evidently huge, at least for software
> implementations.
Well you can only change the sbox to keep the security design the
same. Otherwise it is not Rijndael (well the security model of it
anyways).
> 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.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: Rijndael applications
From: [EMAIL PROTECTED] (Sami J. M�kinen)
Date: Wed, 29 Nov 2000 12:49:30 GMT
[EMAIL PROTECTED] (Red Shadow) wrote in
<YEWU5.59$[EMAIL PROTECTED]>:
>I'm a student of the university in Ghent and I'm writing a presenation on
>Rijndael. I'm looking for some application or some systeem who are already
>using this algoritme.
http://www.geocities.com/sbcarchiver/
I couldn't resist the chance to spam.
Regards,
Sami J. M�kinen / [EMAIL PROTECTED]
--
SBC Cryptographic file compressor/archiver homepage:
www.geocities.com/sbcarchiver/
------------------------------
From: Robert Harley <[EMAIL PROTECTED]>
Subject: Re: Isomorphic Elliptic Curves
Date: 29 Nov 2000 15:15:26 +0100
Bob Silverman <[EMAIL PROTECTED]> writes:
> "J. Rostand" wrote:
> > 1) What is the definition of E1 being isomorphic to E2?
>
> [...]
> Two curves are isomorphic iff they have the same j-invariant.
This is a property (which holds over an algebraic closure) but it is
not the definition. The definition is that two curves are isomorphic
iff there are regular rational maps from E1 to E2 and back which are
inverses of each other.
Bye,
Rob
.-. [EMAIL PROTECTED] .-.
/ \ .-. .-. / \
/ \ / \ .-. _ .-. / \ / \
/ \ / \ / \ / \ / \ / \ / \
/ \ / \ / `-' `-' \ / \ / \
\ / `-' `-' \ /
`-' http://www.xent.com/~harley/ `-'
------------------------------
From: Ed L Cashin <[EMAIL PROTECTED]>
Subject: Re: collision probability with file checksums
Date: 29 Nov 2000 09:45:48 -0500
Bryan Olson <[EMAIL PROTECTED]> writes:
> Ed L Cashin wrote:
> > Bryan Olson writes:
> [...]
> > > Incidentally, a good manipulation detection code must be collision
> > > resistant. Otherwise an attacker might be able to construct an
> > > innocuous file and a malicious file with the same digest, legally
> > > introduce the innocuous file, and then substitute the malicious file
> > > without detection of the substitution.
> >
> > Happily, the idea of a legal introduction is not realistic in file
> > integrity verification systems. If the file is being monitored for
> > manipulation, say it's /bin/ls, then introducing your own /bin/ls is
> > never a legal file introduction. There should be no opportunity for
> > such undetected file placement.
>
> You misunderstand the attack. The potential attacker is an
> insider - the author of the file. Legal introduction means
> the normal and legitimate procedure for installing this
> (perfectly good) file on the system. The effect of the
> attack is that the author can bypass reviews and audits, and
> probably fool post-break forensics.
Indeed, I misunderstood what you were suggesting. I hadn't thought of
the insider attacker scenario, so much thanks for the eye opener!
> Files provided by a vendor and installed with the system are
> unlikely to be good targets for the attack. Far more
> dangerous are the local scripts that configure the host for
> its applications.
Well, if there's a script whose checksum suddenly doesn't match, I
just go read the script. Easy to see that there's no attack going on
-- either planting a file with a checksum found with a birthday-attack
with hopes to replacing the file later, or an outright malicious
script.
But if it's a binary file, the odds are that I'm going to have to call
my peers up, ask if they've replaced that file, and then trust their
good intentions if they say they modified it for some reason.
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?
The same question is relevant to the non-birthday attack, where the
attacker attempts to find file contents whose checksum matches an
already-known checksum, with 2^n difficulty.
--
--Ed Cashin PGP public key:
[EMAIL PROTECTED] http://www.coe.uga.edu/~ecashin/pgp/
------------------------------
From: [EMAIL PROTECTED]
Subject: keysize for equivalent security for symmetric and asymmetric keys
Date: Wed, 29 Nov 2000 14:39:26 GMT
it is generally accepted that an asymmetric 3000 bit key has a security
equivalent to that of a 128 bit symmetric key.
what is the function that can predict the size equivalence, i.e, given
the size of one, it would be possible to predict the size of the other.
any explanations or references to how this is derived?
have checked in the Handbook of Applied Crypto, and all i could find is
one paragraph {remark 1.53 p.32 } explaining in general terms that
asymmetric keys need to be much bigger because the mode of attack can
be through 'factoring' which is much less than exhaustive key-searching
required for symmetric keys.
thanks in advance,
vedaal
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: JCA <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Wed, 29 Nov 2000 07:11:37 -0800
[EMAIL PROTECTED] wrote:
> it is generally accepted that an asymmetric 3000 bit key has a security
> equivalent to that of a 128 bit symmetric key.
>
It depends - RSA requires longer keys than ECC. You might like to
look into Lenstra and Verheul's "Selecting Cryptographic Key Sizes"
paper.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 29 Nov 2000 15:26:46 GMT
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
There are a few papers accessible and this is an area of varying opinions, as
it is all based on extrapolation into higher and higher levels of
infeasibility. One is mine "ECC, Future Resiliency and High Security Systems"
available at www.certicom.com in the white papers section. This gives a chart
based on TIME metric and includes data supplied by NIST (read NSA).
Also, see www.cryptosavvy.com where at least one interpretation of what they
say is that ECC is better than the NIST numbers and RSA/DSA is worse.
Also see RSA Labs paper by Bob Silverman, where he tries to use a COST model.
So you picks your model and makes your mapping. I personally favor the NIST
numbers, as the mapping is very straightforward, but others disagree.
Don Johnson
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: collision probability with file checksums
Date: Wed, 29 Nov 2000 08:30:21 -0700
Ed L Cashin wrote:
<snip>
> 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?
<snip>
Not especially. An easy way to construct lots of files that all
do the same (useful) thing is to include a "serial number" in it
somewhere, which we then set to 2^k possible values. A more
subtle trick might be to place blank lines, or omit them, in
k spots.
JM
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 29 Nov 2000 15:40:38 GMT
Subject: Re: collision probability with file checksums
and do not forget no-ops places in random places.
Don Johnson
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Public key encryption in Javascript?
Date: Wed, 29 Nov 2000 16:02:30 GMT
> Have a look at the source code behind:
>
http://www.frontiernet.net/~jmb184/interests/sci.crypt/small_num_expont.
html
> which impliments modular exponentiation in javascript
Thanks... This is very interesting and fun... I'm not sure it's useful,
but it is fun!
j
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: collision probability with file checksums
Date: 29 Nov 2000 16:25:27 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Bryan Olson wrote:
>The application here is a Tripwire-like system, which does
>not correspond well to either PK signatures or MAC's. The
>goal of the system is to detect and report changes in a set
>of files. Tripwire is useful (perhaps most useful) against
>insider attacks, and an author of one of the files is a
>potential attacker.
Ok. I understand now.
If you use an unkeyed hash, then I agree with the need.
Using a keyed MAC would eliminate this threat (the author of
the file won't know the key), but I can see why the need for
a key might not mesh will with the needs of Tripwire.
Thanks for the explanation!
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: DES question: Has this ever been proven before?
Date: 29 Nov 2000 16:28:29 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Francois Grieu wrote:
>I fail to see how. I see that the length of the "leader" is at most n.
>But we would need the exact length of the leader to pinpoint the
>collision, right ?
Let l be the length of the leader and p the period of the cycle.
If a(n) = a(2n) is the first collision you find, then n = l+p and
2n = l+2p, almost always. You can solve these for p.
Once you know l, you can calculate a(l-1) and a(l+p-1), which form
the pre-images of the collision that were looking for.
Again, I agree that distinguished points is a better strategy in
practice -- it improves the constant factor. But I think the above
works, unless I'm missing something (?).
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 29 Nov 2000 16:47:17 GMT
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
To clarify, I prefer the NIST-supplied numbers over the COST (really STORAGE)
model. Recall that ECC and the DSA q value can be broken using TIME and not
much storage, but that breaking RSA or DSA p value needs TIME plus STORAGE for
the known best method. Recall that hashes and symmetric encryption can be
broken using TIME and not much storage. Therefore mapping TIME (to break sym.)
to TIME (to break asym.) is straightforward but mapping TIME (to break sym.) to
STORAGE (to break RSA) involves more assumptions and is not as straightforward
by a long shot as you can imagine. More assumptions means more assumptions
that might be shown to be wrong in the future.
Another way of looking at it: Do I REALLY want to rely on the current
difficulty of solving the GNFS matrix needing lots of storage or might a
breakthru occur where one needs less storage. That is, is it more plausible
that an entirely new alg. might be invented or that an existing alg. (GNFS) be
improved? Who knows? But one can choose to use less assumptions (i.e., TIME)
and therefore have a less chance to be wrong (that is, be more conservative
than perhaps might be needed).
I prefer the NIST ECC numbers over (one interpretation of) cryptosavvy, as NIST
is more conservative for ECC as the mapping is more conservative (NIST: ECC op
cost = Sym. op. cost), which avoids getting into how much faster a sym. op is
over an ECC op. as this relationship is open to how good an implementation is.
That is, a slow ECC and a fast sym. implementation might give better ECC
comparison numbers. However, no one disputes that a sym op is faster than an
asym op. so assuming they are equal is conservative.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: DES question: Has this ever been proven before?
Date: 29 Nov 2000 17:03:47 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Francois Grieu wrote:
>> and you can deduce the length of the "leader" which enters the cycle
>
>I fail to see how.
Oops, apparently I failed, too. (Please ignore my previous post,
if you see it -- it was absolute nonsense.)
Allow me to try again. If a(n) = a(2n), then the period of the cycle
is n [*]. Now we can go back to the beginning and compute a(i),a(i+n)
for i=1,2,3,...; note that the smallest i such that a(i) = a(i+n) is
always less than or equal to n, and moreover a(i-1), a(i+n-1) give the
desired collision. This can all be done in time linear in the length
of the cycle plus the length of the leader.
Did I get it right this time, or did I make any further mistakes?
[*] Well, the period might divide n, but almost always it is n,
if n is the least value such that a(n) = a(2n) and if you are
iterating a random function.
------------------------------
** 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
******************************
