Re: Impossible compression still not possible. [was RE: Debunking the PGP backdoor myth for good. [was RE: Hypothesis: PGP backdoor

2006-08-30 Thread Ondrej Mikle

Dave Korn wrote:

  Of course, I could point out that there is precisely *1* bit of information
in that huge GIF, so even compressing it to 35 bytes isn't a great
achievement... it's one of the set of less-common inputs that grow bigger as a
compromise so that real pictures, which tend to have at least *some*
variation, grow smaller.



OK, according to Shannon's definition of entropy, how much information 
is there in \pi or e or other transcendent number? AFAIK all finite 
strings are in fractional expansion of \pi (take positive integer base 
other than 10 if you want). Sure, the numbers are correlated, because we 
can express \pi or e as infinite series, though only couple of bytes is 
necessary.


But: if you take any finite string, there exists a finite natural number 
as index where the string can be found in \pi. So are there any "random 
strings" at all? What if I can express the digits starting at 2^(2^k)-th 
index analytically in a short, fast algorithm? In case no other can, 
then I have perfect one-time pad, at least for some time, because 
conventional computers will not reach the place in some reasonable time 
(yes, I know, there may be other correlations). The point I am trying to 
make: if I take e.g. a transcendent number and can analytically express 
a part of its fractional expansion, I *might* have a strong key.


The point for this: I am researching an authenticating scheme where keys 
are *programs*, not data. It means that key can change itself over time, 
for example. The strongest keys would therefore be somewhat recursive 
polymorphic code, that enumerates all possible permutations on some 
finite set in some deterministic, though seemingly random order.


I know that there are "short" descriptions for lots of infinite 
structures, the mentioned transcendent numbers, then take Mandelbrot 
set, various IFSs (iterated function systems), quaternions, unmeasurable 
sets, there are lots of possibilities. What I know for sure is that for 
many mathematical structures short descriptions (programs or (partially) 
recursive functions) exist. What I conjecture is that for each finite 
ordered set a short "compression function" exists. The whole trick is 
that it is almost impossible (meaning computationally infeasible) to 
look for the compression functions using a finite deterministic 
algorithm. Though a human can do it.


It will yet take some time until I have some more results about the 
categories of key programs.


Cheers,
  OM

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: Impossible compression still not possible. [was RE: Debunking the PGP backdoor myth for good. [was RE: Hypothesis: PGP backdoor (was: A security bug in PGP products?)]]

2006-08-30 Thread Ondrej Mikle

We are both talking about the same thing :-)

I am not saying there is a finite deterministic algorithm to compress
every string into "small space", there isn't. BTW, thanks for "There
is ***NO*** way round the counting theory." :-)

All I wanted to say is:
For a specific structure (e.g. movie, picture, sound) there is some
"good" compression algorithm.

E.g.: if you take a GIF 65536x65536, all white, with just one pixel
black, it can be compressed into 35 bytes, see here:
http://i.iinfo.cz/urs-att/gif3_6-115626056883166.gif
If you wanted to compress the same picture using JPEG (i.e. discrete
cosine transform), then two things would happen:

The compressed jpeg file would be a) much bigger b) decompressed image
would have "artifacts", because Fourier transform of a pulse is sync
(infinitely many frequencies). Sure, JPEG is a lossy compression, but
good enough for photos and images that don't have a lot of high
frequencies.

Cheers,
 OM

On 8/28/06, Dave Korn <[EMAIL PROTECTED]> wrote:

On 28 August 2006 15:30, Ondrej Mikle wrote:

> Ad. compression algorithm: I conjecture there exists an algorithm (not
> necessarily *finite*) that can compress large numbers
> (strings/files/...) into "small" space, more precisely, it can
> compress number that is N bytes long into O(P(log N)) bytes, for some
> polynomial P.

[  My maths isn't quite up to this.  Is it *necessarily* the case that /any/
polynomial of log N /necessarily/ grows slower than N?  If not, there's
nothing to discuss, because this is then a conventional compression scheme in
which some inputs lead to larger, not smaller, outputs.  Hmm.  It would seem
to me that if P(x)==e^(2x), P(log n) will grow exponentially faster than N.
I'm using log to mean natural log here, substitute 10 for e in that formula if
we're talking about log10, the base isn't important.  However, assuming that
we're only talking about P that *do* grow more slowly, I'll discuss the
problem with this theory anyway.  ]


  There are many, but there are no algorithms that can compress *all* large
numbers into small space; for all compression algorithms, some sets of input
data must result in *larger* output than input.

  There is *no* way round the sheer counting theory aspect of this.  There are
only 2^N unique files of N bits.  If you compress large files of M bits into
small files of N bits, and you decompression algorithm produces deterministic
output, then you can only possibly generate 2^N files from the compressed
ones.

> Take as an example group of Z_p* with p prime (in another words: DLP).
> The triplet (Z, p, generator g) is a compression of a string of p-1
> numbers, each number about log2(p) bits.
>
> (legend: DTM - deterministic Turing machine, NTM - nondeterministic
> Turing machine)
>
> There exists a way (not necessarily fast/polynomial with DTM) that a
> lot of strings can be compressed into the mentioned triplets. There
> are \phi(p-1) different strings that can be compressed with these
> triplets. Exact number of course depends on factorization of p-1.
>
> Decompression is simple: take generator g and compute g, g^2, g^3,
> g^4, ... in Z_p*

  This theory has been advanced many times before.  The "Oh, if I can just
find the right parameters for a PRNG, maybe I can get it to reconstruct my
file as if by magic".  (Or subsitute FFT, or wavelet transform, or
key-expansion algorithm, or ... etc.)

  However, there are only as many unique generators as (2 to the power of the
number of bits it takes to specify your generator) in this scheme.  And that
is the maximum number of unique output files you can generate.

  There is ***NO*** way round the counting theory.

> I conjecture that for every permutation on 1..N there exists a
> function that compresses the permutation into a "short"
> representation.

  I'm afraid to tell you that, as always, you will find the compression stage
easy and the decompression impossible.  There are many many many more
possible permutations of 1..N than the number of unique "short
representations" in the scheme.  There is no way that the smaller number of
"unique representations" can possibly produce any more than the same (smaller)
number of permutations once expanded.  There is no way to represent the other
(vast majority) of permutations.

>  It is possible that only NTM, possibly with infinite
> algorithm (e.g. a human) can do it in some "short finite time".

  Then it's not really an algorithm, it's an ad-hoc collection of different
schemes.  If you're allowed to use a completely different encryption scheme
for every file, I can do better than that: for every file, define an
encryption scheme where the bit '1' stands for the content of that file, and
everything else is represented b

Re: Debunking the PGP backdoor myth for good. [was RE: Hypothesis: PGP backdoor (was: A security bug in PGP products?)]

2006-08-30 Thread Ondrej Mikle

On 8/28/06, Dave Korn <[EMAIL PROTECTED]> wrote:

  The author has made the *exact* same error as when someone comes up with a
magical compression algorithm that they say can compress absolutely any data
down to a tiny size.  They always get the data to compress, sure, but they
always have problems with the decompression stage.  They tend to think that
this is just a minor bug in their decompressor they need more time to work on,
but no amount of time will let them work around the fundamental mathematical
fact that they've not got sufficient information in their compressed file to
reconstruct the original.


Thanks, sorry for the hassle, me (and others) should've checked it
before asking.

Ad. compression algorithm: I conjecture there exists an algorithm (not
necessarily *finite*) that can compress large numbers
(strings/files/...) into "small" space, more precisely, it can
compress number that is N bytes long into O(P(log N)) bytes, for some
polynomial P. Here's a lead:

Take as an example group of Z_p* with p prime (in another words: DLP).
The triplet (Z, p, generator g) is a compression of a string of p-1
numbers, each number about log2(p) bits.

(legend: DTM - deterministic Turing machine, NTM - nondeterministic
Turing machine)

There exists a way (not necessarily fast/polynomial with DTM) that a
lot of strings can be compressed into the mentioned triplets. There
are \phi(p-1) different strings that can be compressed with these
triplets. Exact number of course depends on factorization of p-1.

Decompression is simple: take generator g and compute g, g^2, g^3,
g^4, ... in Z_p*

I conjecture that for every permutation on 1..N there exists a
function that compresses the permutation into a "short"
representation. It is possible that only NTM, possibly with infinite
algorithm (e.g. a human) can do it in some "short finite time". Again,
I could've/should've proven or disproven the conjecture, I just don't
want to do it - yet ;-)

Thanks
 OM

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: Hypothesis: PGP backdoor

2006-08-28 Thread Ondrej Mikle

Len Sassaman wrote:

On Thu, 24 Aug 2006, Ondrej Mikle wrote:
I also have no question, personally, that if there's a backdoor in PGP,
neither Mr. Callas nor any of the PGP engineers I had the pleasure to work
with know of it. Your theory is indeed wild, and though I don't mean to
discourage vigilance in questioning these sorts of potential subversions
of integrity in software as important as PGP, you might consider doing
more research into the background of people against whom you choose to
levy hypothetical accusations in public forums in the future.



OK, thanks for answering. I had only very limited view of the background 
behind PGP (i.e. stuff about NAI/PGP corp).


One last question: what about the PGPdisk SDA (self-decrypting archives, 
i.e. executables)? There has been a claim that SDA archives can be 
decrypted using a debugger. Is it true or false? See the section "Two 
Ways to bypass PGP SDA Authentication and EXTRACT with success" in the 
"advisory" http://www.safehack.com/Advisory/pgp/PGPcrack.html. Is the 
guy confused again? ;-)


Thanks
  OM

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Provably secure cryptosystem

2006-08-27 Thread Ondrej Mikle

Hello.

I humbly say that I *might* have devised a provably secure cryptosystem 
that actually *might* work in reality. It provides secure authentication 
and possibly might be extended to something else. Sounds too good to be 
true? Well, you're right. In reality it's a bit more complicated.


I'm risking again making fool of myself, but what the heck ;-) At least 
I think it's something you all know, at least to some extent.


I have searched for some other provably secure schemas for 
MACs/signatures/etc., they use many similar assumptions (e.g. random 
oracle assumption, strong one-way hash function with uniform 
distribution assumption) and some similar techniques.


In the system I can prove there *is* a random oracle (this is also not 
so entirely true, but...you'll see).



OK, the point:
In complexity theory with random oracle, NP != P (cf. Shoup 1997: Lower 
Bounds for Discrete Logarithms and related problems, Baker-Gill-Solovay 
1975). The trick is based on this fact.


Keys in the cryptosystem are not *data*, but *programs*, i.e. 
(partially) recursive functions. The trick is to simulate random oracle 
by a program, each program is the key describing a random permutation on 
some subset of natural numbers.


The cryptosystem is based on the following observation (extension of 
halting problem):
Given a program L as an input that takes 1..n as input, L stops exactly 
for one 1<=j <=n.
If we give this program to a DTM (deterministic Turing machine), no 
finite algorithm can decide for all possible input programs L and 
numbers n, for which j the input program L will stop in polynomial time.


In another words, no finite program can detect every virus (virus is 
defined to be a self-replicating program) or check if other program will 
draw prescribed picture for a given input, etc. in polynomial time.


So, the paper can be found here (alpha-draft, by no means complete, some 
parts such as related work and references, acks are not complete):


--
http://urtax.ms.mff.cuni.cz/~abyssal/PS.pdf
--

Be warned, it may be at least *partially* false, because I 
*deliberately* left out one proof ("protecting the keyspace", though 
it's security by obscurity). Well, hopefully there are no more serious 
glitches ;-]


The system as whole is secure, but every single instance can be of 
course broken by man (stealing the key, guessing the key, 
cryptanalysis). Integer factorization problem, (generalized) discrete 
logarithm problem are also elements of the system (it is a set).


At least I hope you'll have some fun.

OM

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Hypothesis: PGP backdoor (was: A security bug in PGP products?)

2006-08-27 Thread Ondrej Mikle

Hello.

We discussed with V. Klima about the "recent" bug in PGPdisk that 
allowed extraction of key and data without the knowledge of passphrase. 
The result is a *very*wild*hypothesis*.


Cf. http://www.safehack.com/Advisory/pgp/PGPcrack.html

Question 1: why haven't anybody noticed in three months? Why has not 
there been a serious notice about it?


According to the paper, both "standard" .pgd and self-extracting SDA 
(self-decrypting archives) are affected. Systematic backdoor maybe?


Possibilities:
1) it is a hoax. Though with very low probability. The text seems to 
include a lot of work and makes perfect sense (REPE CMPS, all the 
assembly), i.e. we suppose it is highly improbable that somebody would 
make such hoax. This can be either proven or disproven simply by 
checking the Win program using hex editor/debugger (using an already 
downloaded copy). I haven't had the time to check it yet (no Win).


2) AFAIK, Zimmerman is no longer in control of the company making PGP. 
AFAIK the company (NAI) has been bought by another group couple of years 
ago.


www.pgp.org says:

"
2002/03/08 - NAI drops PGP Desktop
2001/10/15 - NAI to sell PGP division
"

It may be therefore quite possible that NSA/CIA/FBI/etc. couldn't force 
Zimmerman to compromise his own product directly, so they have bought 
the company. The backdoor might have been introduced in the latest 
releases (e.g. 8.x, 9.x).


3) there was a lazy programmer, or a programmer-infiltrator from the 
ranks of intelligence services. What does one do when a cryptosystem 
seems unbreakable? He circumvents it. AFAIK the code has been checked 
many times in NAI, until some point in time.


As you all probably know, there has been a lot of mischief around 
Zimmerman and PGP in the '90-ties. We don't think NSA/CIA/FBI/etc would 
"just give up without fight". You know, the "three-line PERL RSA 
implementations on T-shirts" and so on.


Code of PGPdisk 9.x looks like this according to the paper: when the 
passphrase is changed, the key itself remains untouched. If at least the 
encryption key has been encrypted by a symmetric key generated e.g. by 
PBDFK2 from the passphrase.



Conclusion: it seems that NSA/CIA/FBI/etc. haven't called truce. 
Thought, very clever solution. Nevertheless, nothing we haven't had 
already seen in 1st/2nd world war tactics.


What do you think? Your input is welcome.

OM

P.S. sorry for any misspellings of names


-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: A security bug in PGP products?

2006-08-22 Thread Ondrej Mikle

Max A. wrote:

Hello!

Could anybody familiar with PGP products look at the following page
and explain in brief what it is about and what are consequences of the
described bug?

http://www.safehack.com/Advisory/pgp/PGPcrack.html



It seemed a bit obscure to me at first, but it says basically:

PGPdisk does not use key derived from passphrase, just does simply this:

if (somehash(entered_password) == stored_password_hashed) then 
access_granted();


That's the REPE CMPS chain instruction (string comparison). The check 
can be simply skipped using debugger by interrupting the program, 
changing CS:EIP (i.e. the place of execution) to resume after 
"successful" check. The text probably implies that the key is stored 
somewhere in the PGPdisk file and key's successful extraction does not 
depend on knowledge of the passphrase.


So if you change passphrase, the disk won't get re-encrypted, just by 
copy&pasting the old bytes you will revert to the old passphrase or you 
can create another disk with passphrase chosen by you and use 
copy&pasting method to decrypt other PGPdisk protected with passphrase.


I haven't checked myself if their claim is true, but it's possible.

Hope that helped
  O. Mikle

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: Factorization polynomially reducible to discrete log - known

2006-07-12 Thread Ondrej Mikle

David Wagner wrote:

The algorithm is very simple:
1. Choose a big random value x from some very broad range
  (say, {1,2,..,N^2}).
2. Pick a random element g (mod N).
3. Compute y = g^x (mod N).
4. Ask for the discrete log of y to the base g, and get back some
  answer x' such that y = g^x' (mod N).
5. Compute x-x'.  Note that x-x' is a multiple of phi(N), and
  it is highly likely that x-x' is non-zero.  It is well-known
  that given a non-zero multiple of phi(N), you can factor N in
  polynomial time.
Not exactly. Consider N = 3*7 = 21, phi(N) = 12, g = 4, x = 2, x' = 5. 
You'll only get a multiple of phi(N) if g was a generator of the 
multiplicative group Z_N^*.


When N is a large RSA modulus, there is a non-trivial probability that g
will be a generator (or that g will be such that x-x' lets you factor N).
The above is good enough for a polytime reduction.



Actually, you can never get a generator of Z_N^* unless p=q, because 
when p != q, it is not a cyclic group (this error was in my proof, too). 
Though with great probability you get an element of high order. It is 
enough doing lcm() to get the phi(N) and it will run in polynomial time.


I noted the fact IFP(N) to DLOG in Z_N^* is really mentioned in Handbook 
of Applied Crypto, but without proof or algorithm, just two lines (I 
guess that's why I missed/didn't remember it).


-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: hashes in p2p, was Re: switching from SHA-1 to Tiger ?

2006-07-12 Thread Ondrej Mikle

Travis H. wrote:

On 7/11/06, Zooko O'Whielacronx <[EMAIL PROTECTED]> wrote:

I hope that the hash function designers will be aware that hash
functions are being used in more and more contexts outside of the
traditional digital signatures and MACs.  These new contexts include
filesystems like ZFS [3], decentralized revision control systems like
Monotone [4], git [5], mercurial [6] and bazaar-ng [7], and peer-to-peer
file-sharing systems such as Direct Connect, Gnutella, and Bitzi [6].


MD4/5 are commonly used as a unique fixed-size identifier of an
arbitrarily-chosen* length of data in p2p file systems, and we are all
aware of the collision attacks.  They bring up some interesting points
to consider:

1) What semantics can one induce by using a collision attack, given
the existing protocols/clients?  There are some rumors the MPAA or
RIAA is using protocol-level attacks to "poison" p2p networks like
bittorrent and KaZaa.  Can cryptanalysis results be playing a part?


RIAA uses only very basic cryptanalytic attacks. Specifically, Kazaa 
(FastTrack protocol) uses very stupid UUHash algorithm, which works like 
this: first 300kB are hashed with MD5, then 300 kB at 1MB boundary is 
added to hash, then 300 kB at 2MB boundary, then 300kB at each 2^n MB 
boundary. It is clear that it is very easy to generate collisions for 
UUHash.


For other networks, mostly sybil attacks are used (spawning a lot of 
fake nodes and fake files with the same name so that search turns them up).



2) How do we refactor these widely deployed systems with a new,
stronger hash function?


An example how to handle this might be aMule and eMule clients. The 
basic ed2k protocol only uses MD4 hashes (it is hash list, the hash in 
magnet link is the MD4 hash of MD4 hashes of file blocks). These two 
clients add protocol extension called AICH algorithm (basically it is 
Merkle tree of SHA-1 hashes). The root hash might be a part of magnet 
link, but does not have to be (since it is not part of the original 
protocol).


If the root hash is part of the magnet link, then the received tree can 
be checked. If it is not part of the magnet link, then the client 
attempts to retrieve it from clients that support AICH. If at least 10 
clients send the same root hash and if that is at least 92% of all 
received root hashes, such root hash is considered trusted for the 
current session. It is definitely not 100% secure, but the more clients 
support AICH, the more often you will find the root hash in magnet link 
(thus being able to check the received tree). Even in the absence of 
root hash in magnet link, the attacker needs to control significant 
portion of network to be able to spoof the root hash with some high 
probability.


A simple concept that would allow replacing the hash functions would be 
adding optional parameters to protocol specification. Then users can 
switch clients "continuosly", i.e. users with old clients will not be 
cut off of the network each time hash function changes.



-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: Factorization polynomially reducible to discrete log - known fact or not?

2006-07-11 Thread Ondrej Mikle

Charlie Kaufman wrote:

I believe this has been "known" for a long time, though I have never seen the 
proof. I could imagine constructing one based on quadratic sieve.

I believe that a proof that the discrete log problem is polynomially reducible 
to the factorization problem is much harder and more recent (as in sometime in 
the last 20 years). I've never seen that proof either.

--Charlie



OK, I had the proof checked. I put it here: 
http://www.ms.mff.cuni.cz/~miklo1am/Factorization_to_DLog.pdf


Warning: it may be not what you'd expect.

First of all, it reduces the factorization to a discrete log in a group 
of unknown order (or put in another words: you'd need to factorize to 
learn the group order). It has been proven by V. Shoup that when group 
operation and the inverse are the only operations that can be done with 
group elements, then the best algorithm can be O(sqrt(n)), where n is 
the number of elements. I guess then the group of Z_N* (where N=pq) of 
unknown order qualifies for this if we don't want to use factorization 
(actually you can't compute inverse group operation here). In the light 
of this fact, is this proof of any use?


Even if the proof is not useful, is the "generator picking lemma" (lemma 
2) anything new? It states basically this:
In any cyclic group of order n there is at least 1/log2(n) probability 
of picking a generator randomly and thus generator can be found in 
polynomial time with overwhelming probability of success.


The only facts close to this lemma I found were:
1) Product phi(p_i)/p_i for consecutive primes p_i approaches zero as 
more and factors are added to the product (phi is Euler phi function). 
The lemma states a lower bound for the product.
2) "If the generalized Riemann hypothesis is true, then for every prime 
number p, there exists a primitive root modulo p that is less than 70 
(ln(p))^2." (http://en.wikipedia.org/wiki/Primitive_root_modulo_n)


Charlie:
Thanks for answering my second question which I have not asked yet :-) 
(the reduction in opposite direction). I'm also working on the opposite 
reduction, but I'm at best halfway through (and not sure if I am able to 
finish it).


Last question:
Joseph Ashwood mentioned someone who claimed to have algorithm for 
factorization and had only the reduction to DLP. Anyone knows where I 
could find the algorithm? Or maybe name of the person, so I could search 
the web.


Thanks
  O. Mikle

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Factorization polynomially reducible to discrete log - known fact or not?

2006-07-09 Thread Ondrej Mikle

Hello.

I believe I have the proof that factorization of N=p*q (p, q prime) is 
polynomially reducible to discrete logarithm problem. Is it a known fact 
or not? I searched for such proof, but only found that the two problems 
are believed to be equivalent (i.e. no proof).


I still might have some error in the proof, so it needs to be checked by 
someone yet. I'd like to know if it is already known (in that case there 
would be no reason to bother with it).


Thanks
  O. Mikle

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: expanding a password into many keys

2005-06-13 Thread Ondrej Mikle
On 6/12/05, Ian G <[EMAIL PROTECTED]> wrote:
> I'd like to take a password and expand it into
> several keys.  It seems like a fairly simple operation
> of hashing the concatonatonation of the password
> with each key name in turn to get each key.
> 
> Are there any 'gotchas' with that?
> 
> iang
> 

I guess you should use some scheme like PKCS #5 PBKDF2 scheme
(password based key derivation function). The only difference between
your idea and PBKDF2 is that the latter does a lot of hash rounds and
is salted (I guess you pick key name to be static and not random, so
they are not used as salts).
Salting helps a bit against static precomputed hashes and techniques
like rainbow tables.

Ondrej Mikle

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: Collisions for hash functions: how to exlain them to your boss

2005-06-13 Thread Ondrej Mikle
On 6/13/05, Eric Rescorla <[EMAIL PROTECTED]> wrote:
> While this is a clever idea, I'm not sure that it means what you imply
> it means. The primary thing that makes your attack work is that the
> victim is signing a program which he is only able to observe mediated
> through his viewer. But once you're willing to do that, you've got a
> problem even in the absence of collisions, because it's easy to write
> a program which shows different users different content even if you
> without hash collisions. You just need to be able to write
> conditionals.

Well, it's partially true.
1)
It is possible to create a program that does exactly the same without
the need of collisions

2)
A program creating similar effect without the use of collisions must
use some external data to make decision. Therefore, it is possible to
prove that it may (under some circumstances) behave in a different
way. If you have a program that has all the data hard-coded (i.e.
static, internal), it will behave provably only in the prescribed way.
(Of course some strange 'if' may cause suspicion).
That's where the collision comes in. For one version of the PostScript
document, it can be proven that it will always display the same thing
(no matter what date or what user, provided that it is interpreted
with an interpreter compliant to postscript specification). The
problem arises when a person believes that by signing the program, it
will be the same code (which was proven to do exactly one thing) that
matches the signature next time the signature will be checked. Which
it won't, because of collisions. You can't accomplish this without use
of collisions.

3)
There is also a psychical point of view - most people don't know that
postscript files are actually code. So are PDFs. Strength of
post-script part of language was cut down, but there is javascript,
however not many viewers except Adobe reader support it. Other
'code/data' formats are e.g. MS Excel, MS Word, OpenOffice Writer
files, in fact almost any complex file format.
This is something you can't do on paper (well, except for some tricks
like invisible inks that become visible after some time).
I've had a talk on this a few months ago with a couple of other
cryptographers. The result was that there is no such thing as 'unique
representation of document' like it is for a plain old sheet of paper.
It depends on viewer application.

4)
You don't even need conditionals. For one conference I've created an a
pair of Excel spreadsheets that used a simple sum over a couple of
fields. I picked Excel, because it is widely known application. Both
files had identical md5 hash, but different result. There was no need
for scripting.
It works like this: you put some believable numbers on the sheet, then
create a region colored white letters on white background ;-)
You create a collision in the region, so the nonsense numbers are not
visible. On the next row, you are 'behind' the collision (in terms of
position in the file data stream). So you put anything you want in
both files in the next rows, it only has to be the same for both
colliding files. So create another region with white on white, put
some 'bulgarian constants' (*) in there and put a SUM or some
unsuspicious operation as one of the visible items.
Now both xls's have the same md5 hash, but each displays something
else even without the use of VisualBasic scripts.
Sure, you can create white on white document without the use of
collisions, but then either
a) you have to use scripting with external-data-based conditionals or
b) you can't make their hashes equal without use of collisions

(*) def. 'bulgarian constant' - a number you add to your result if it
doesn't match the expected result :-)

5)
Most document formats cannot be viewed without a viewer application
(unless you make an effort to decode it by hand, which most people
won't or can't).

Ondrej Mikle

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: The Pointlessness of the MD5 "attacks"

2004-12-22 Thread Ondrej Mikle
f the security hole to
spammers, virus writers, etc. I'm not saying the MD5 collision allows
for a highly practical attack (at least the example involves an
insider), but when we know it's possible, why should we continue using
MD5?

Ondrej Mikle

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: The Pointlessness of the MD5 "attacks"

2004-12-14 Thread Ondrej Mikle
On Tue, 14 Dec 2004 14:43:24 +, Ben Laurie <[EMAIL PROTECTED]> wrote:
> But the only way I can see to exploit this would be to have code that
> did different things based on the contents of some bitmap. My contention
> is that if the code is open, then it will be obvious that it does
> "something bad" if a bit is tweaked, and so will be suspicious, even if
> the "something bad" is not triggered in the version seen.

There are many ways to obfuscate code so tha it will seem innocent,
see for example International Obfuscated C Code Contest
(http://www.ioccc.org/main.html). It can be based on variable
modification using buffer overflows, integer overflows, strange side
effects of expression evaluation, etc.

Another possibility for an attacker is the use of deliberate and very
rare race conditions, which only attacker knows how to trigger. Race
conditions are very difficult to discover. Cf. Linux ptrace race
condition (http://archives.neohapsis.com/archives/bugtraq/2001-10/0135.html).
It's been there in kernels 2.2.0 - 2.2.19 and 2.4.0 to 2.4.9. It
allowed for local privilege escalation. Took quite a long time to
discover it, even though it was open source code. Quite a long time
for opportunity, if we assumed an attacker would do similar attack
deliberately.

> So, to exploit this successfully, you need code that cannot or will not
> be inspected. My contention is that any such code is untrusted anyway,
> so being able to change its behaviour on the basis of embedded bitmap
> changes is a parlour trick.

That's true in theory, but it's different in real world. Take
Microsoft software as an example. Many banks use their software (and
sometimes even military). I don't think that all of them reviewed
Microsoft's source code (I guess only a few, if any at all). There was
an incident of a worm attacking ATMs.

Another example, Enigma was being sold after WW 2, but the Allies knew
it could be broken. The purchasers did not. Same as when US army sold
some radio communications that used frequency hopping to Iraq during
1980's. US knew that it could be broken ("just in case...").

Ondrej Mikle

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Some notes to "MD5 To Be Considered Harmful Someday" - practical uses, additional attacks

2004-12-08 Thread Ondrej Mikle
I've read the paper. What is stunning, that I've written similar paper
named "Practical Attacks on Digital Signatures Using MD5 Message
Digest" using very similar techniques only recently. It was submitted
to Cryptology ePrint Archive (http://eprint.iacr.org) a week ago, on
December 2nd. They will probably publish it in a day or two (I guess),
they are processing december papers right now.

The difference is that I've focused mainly on practical attacks in
software distribution channel (there is an attack scenario depicted).
The attack scenario is based on talks with a couple of
developers/packagers on how the software packaging and distribution
works.

The paper describes an example of pair of executables and data files
which have same MD5 sum, but extract different contracts. Then, there
is the idea and practical demonstration of a tool that creates custom
(self-)extract packages which can contain arbitrary files, again both
with identical MD5 sums, each extracting another one. Lastly, there is
notion how it could be made even more effective when the algorithm to
find MD5 collisions for any initialization vector is published.

Most Windows software is distributed as self-extract (self-install)
executables. In Linux world, self-extract executables are not so
common. Formats tar.gz, tar.bz2, zip and various packages (rpm, deb,
etc.) prevail. After submitting the paper we've been inspecting if
similar attack could be made on these formats. Well, definitely yes
for zip, tar.bz2 and tar.gz. The only problem was to find concurrent
collision in MD5 and CRC32, which is not that hard after all
(estimated time is approx. 320 hours using a single PC like the one on
your table, or less than one day on 16 PCs). For rpm, deb packages,
the trick is to put the colliding block somewhere in the header, where
it is not checked internally by the package manager for any checksum.

The paper, source codes, examples and attacks on zip/gzip/.../rpm/...
formats can be found at:
http://cryptography.hyperlink.cz/2004/collisions.htm

We think that these attacks could be used even today, but they are not
so hard to spot when people are aware of them.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]