Cryptography-Digest Digest #884, Volume #11 Mon, 29 May 00 07:13:01 EDT
Contents:
Re: Crypto patentability (Mok-Kong Shen)
Re: On dynamic random selection of encryption algorithms (Mok-Kong Shen)
Re: Hill's algorithm (Mok-Kong Shen)
Re: No-Key Encryption (Mok-Kong Shen)
Re: No-Key Encryption (Mok-Kong Shen)
Re: Crypto patentability (Mok-Kong Shen)
Re: MD5 win32 / linux compatibility ([EMAIL PROTECTED])
Re: Matrix key distribution? (Benjamin Goldberg)
Use of wasted symmetric key bandwidth in key agreement protocols (Mark Currie)
Re: Hill's algorithm (Benjamin Goldberg)
Re: Math problem (P=NP) prize and breaking encryption ("Douglas A. Gwyn")
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (David Boothroyd)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (David Boothroyd)
Re: Another sci.crypt Cipher (tomstd)
Re: Refs to "Hillclimbing" and other algorithms? ([EMAIL PROTECTED])
Re: On dynamic random selection of encryption algorithms ("Dan Kaminsky")
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Adrian Kennard)
Re: Math problem (P=NP) prize and breaking encryption (Boris Kolar)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Crypto patentability
Date: Mon, 29 May 2000 09:54:11 +0200
zapzing wrote:
> But here in the United States it is universally
> recognized that political action takes both time
> and *Money* . Anyone who could affort to mount
> such an attack would *Necessarily* have an
> economic stake on doing so, and would therefore
> be susceptible to the argument that they were
> doing it "for the money".
I am not quite sure of that. See the work of EFF and other
organizations for freedom of privacy.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On dynamic random selection of encryption algorithms
Date: Mon, 29 May 2000 09:56:12 +0200
Addendum:
6. If the constituent ciphers are parametrized, the parameters
can be supplied dynamically by the PRNG.
7. The output of the PRNG can be influenced, if one wishes, by
the encryption process dynamically, e.g. through some hash
value of the previous block. This further complicates the
task of the analyst.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Hill's algorithm
Date: Mon, 29 May 2000 09:54:00 +0200
Mark Wooding wrote:
> It's also normally understood that a block cipher keyspace is flat. If
> the matrix is based on key material, I suspect that there will be many
> subtle (and not-so subtle) differently strong keys.
The problem with Hill's method lies more in the fact that, if a pair of
plaintext and ciphertext is available, then the matrix can be recovered.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Mon, 29 May 2000 09:53:52 +0200
Michael Pellaton wrote:
> It seems to me that I used the wrong name of a method of encryption.
> Maybe it's an error that occurred during translation from and to
> German (I have seen the word "no-key encryption" in at least two
> German books).
Could you please give the German word and, in particular, name the
two books?
[snip]
> It allows two people or systems to communicate safely without knowing
> anything about eachother except for the fact that it uses the
> same encryption system.
>
> I know that XOR is a very weak encryption methode and I just used it
> to show what I mean with "No-Key encryption" in an easy way.
>
> Now, what's the proper English name for what I described above?
> Where is it used?
> Are there any well-known implementations?
The scheme is probably what initiated the idea of current public key
systems. It apparently has no specific name and is described on p.63 of
A. Salomaa, Public-Key Crpytography. Springer-Verlag, 1990.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Mon, 29 May 2000 09:58:54 +0200
Steve Roberts wrote:
> Er, ROT-13 *does* have a key - it's the "13" in the name. Maybe it
> could be called "Known-Key Encryption"
> Watch out for my new improved cipher ROT-X, which does not have this
> weakness.... .....
Yes. (Private) key is a piece of secret, not assumed to be
available to the public. A codebook is also secret and
equivalent to 'key' (one chooses the mapping or even chooses
a codebook from several). Hence 'no-key encryption' excludes
all such stuffs. What remains is, as Boris Kazak pointed
out, language translations. Anyone having travelled a lot
knows how cryptic foreign languages could be. If your
opponent doesn't have the expertise or can't catch up with
the required knowledge fast enough, then he is out. Kahn
told that in WWII the British army used soldiers with foreign
native languages to transmit commands verbally. In countries
where there are very different dialects, switching to another
dialect could have similar benefits. BTW, one sees here
one concrete reason why having a universal language of the
world is not a good idea, as long as there is no freedom
of privacy.
M. K. Shen
=============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Crypto patentability
Date: Mon, 29 May 2000 10:07:14 +0200
Anders Thulin wrote:
> It's not the operation in itself that's patented, but the use to which it is
> put.
That's o.k. Nevertheless there can be discussed what should and what
should not be awarded patents, I believe. If an operation is used in
a specific piece of software and the software is patented, I have no
personal objection at all. The issue is whether I am free to use that
same (primitive) operation in a different piece of software.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: MD5 win32 / linux compatibility
Date: Mon, 29 May 2000 08:10:04 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Runu Knips wrote:
> You have 'md5sum' on many linux systems. Its output is 100% trustable
actually its
100% * ( 1 - 2^-128 ) = 99.99999999999999999999999999999999999970612641 % trustable
== <EOF> ==
Disastry http://i.am/disastry/
http://disastry.dhs.org/pgp.htm <-- PGP half-Plugin for Netscape
http://disastry.dhs.org/pegwit <-- Pegwit - simple alternative for PGP
remove .NOSPAM.NET for email reply
=====BEGIN PGP SIGNATURE=====
Version: Netscape PGP half-Plugin 0.14 by Disastry / PGPsdk v1.7.1
iQA/AwUBOTIJtTBaTVEuJQxkEQJVxACg6ErTTYnrRaeO+9oI3hKFNxZt0qcAn0q3
mgPFm4WfAKtw6ZAyrdhuAuaV
=QFxf
=====END PGP SIGNATURE=====
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Matrix key distribution?
Date: Mon, 29 May 2000 08:29:58 GMT
tomstd wrote in <news:[EMAIL PROTECTED]>:
>
> In article <[EMAIL PROTECTED]>, Benjamin Goldberg
> <[EMAIL PROTECTED]> wrote:
> >Michael Brown wrote:
> >>
> >> Benjamin Goldberg <[EMAIL PROTECTED]> wrote in article
> >> <[EMAIL PROTECTED]>...
> >> > Perhaps this seems like a silly question, but what if matrix C isn't in
> >> > any special format, but whose only property is that it's non-invertable?
> >> For C to be singular either one (or more) row(s) has to be a combination of
> >> the other rows or one (or more) column(s) have to be a multiple of the
> >> other columns. The matrix C is based on the first idea with the second row
> >> being a multiple, in this case m, of the first row. I suspect that is still
> >> would be insecure if the matrix C used the other method though.
> >
> >Don't forget that we're working in modulo 2^32 ... There is therefor
> >another,
> >simpler way to make C be non-invertable: Make all 4 numbers even.
> >
> >
>
> But then all the output numbers will be even. That may not be a
> desirable property.
While it's true that all the numbers in C will be even, there is no
reason, once the key exchange is complete, for it to be used as a
matrix... it's just 4 numbers which happen to be even, but which
have no other special properties; All you need to do is put them
through a hash before using them.
------------------------------
Subject: Use of wasted symmetric key bandwidth in key agreement protocols
From: [EMAIL PROTECTED] (Mark Currie)
Date: 29 May 2000 08:29:16 GMT
Hi,
In a communications security application involving an on-line key agreement
protocol, there often exists additional keying bandwidth which is not generaly
used. As an example, if the key exchange protocol involved the use of
Diffie-Hellman, the typical length of the resultant mutual secret value could
be in the order of 128 bytes. Only 16 - 32 bytes are typically required for use
as a secret key for data encryption. These bytes can either be directly
extracted from or be the result of hashing the 128 bytes. I have often wondered
how the wasted bytes could be put to good use. One idea is to use them to
modify the symmetric algorithm used to encrypt the data in some way. However,
if not applied correctly, it can in fact weaken the algorithm even if these
values are secret. Another idea could be to use it in the key expansion part of
an algorithm to effectively increase key entropy while not impacting on
performance.
I would be interested in any other idea's for the use of these often wasted
bytes to increase data security without (ideally) impacting on the data
encryption performance.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Hill's algorithm
Date: Mon, 29 May 2000 08:44:36 GMT
Mok-Kong Shen wrote:
>
> Mark Wooding wrote:
>
> > It's also normally understood that a block cipher keyspace is flat. If
> > the matrix is based on key material, I suspect that there will be many
> > subtle (and not-so subtle) differently strong keys.
>
> The problem with Hill's method lies more in the fact that, if a pair of
> plaintext and ciphertext is available, then the matrix can be recovered.
How? Please keep in mind that I'm not using a "pure" Hill's cipher.
I'm doing 8 rounds of whitening, matrix multiplication, and diffusion.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: Mon, 29 May 2000 08:47:10 GMT
David A Molnar wrote:
> It's more than that. A constructive proof that P = NP which
> took the form of a very efficient (i.e. low polynomial time)
> algorithm for solving any problem in NP would change the world.
> Not just in cryptography, either.
I don't think a nonconstructive proof of P=NP would make much
difference in practice, and I rather doubt that a single
algorithm could be "very efficient" as you have defined it for
*all* problems in NP. (In fact I think I could prove not --
basically that would imply that all P problems are low-P.)
Remember that this sort of "complexity" is only in the limit
of infinitely large N, and is worst-case, and requires exact
solutions. We already know of an efficient algorithm for
*closely approximating* the solution for at least one NPC
problem. For some applications, that is good enough.
------------------------------
From: [EMAIL PROTECTED] (David Boothroyd)
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Mon, 29 May 2000 10:58:09 +0000
In article <[EMAIL PROTECTED]>, Bob
<[EMAIL PROTECTED]> wrote:
> > The proposals in the Bill are exactly the same as the ones Labour suggested
> > before the election so there really isn't anything for anyone to get
> > worked up about.
>
> They didn't exactly go out of their way to publicise this gross human
> rights violation though, did they.
It is not a human rights violation. The s.19 certificate states that the
Bill complies with all the UK's human rights obligations.
> How many voters actually got hold of and read the huge full manifesto
> document?
It was not huge. Since 1983 Labour manifestos have not been huge. However
it is not the job of the manifesto to include the complete range of
policies the party intends to introduce.
------------------------------
From: [EMAIL PROTECTED] (David Boothroyd)
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Mon, 29 May 2000 11:00:36 +0000
In article <8gs8pa$hf5$[EMAIL PROTECTED]>, "Anarchist Lemming"
<[EMAIL PROTECTED]> wrote:
> "David Boothroyd" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > The proposals in the Bill are exactly the same as the ones Labour
> suggested
> > before the election so there really isn't anything for anyone to get
> > worked up about. The Conservatives were planning mandatory key escrow.
>
> Wrong. We have every right to get worked up. I wasn't old enough to vote in
> the last election (not that I would have) and if it becomes law I could be
> facing up to 2 years imprisonment.
The answer is simple: Don't break the law.
> Just because they have an electoral "mandate" doesn't mean it's useless
> to fight against this kind of legislation. Remember, we stopped the Poll
> Tax.
I thought you said you were too young. The Poll Tax was replaced because
Conservative MPs realised it was too unpopular. The idea that the police
being able to demand that encrypted data (about which they have a reasonable
suspicion) be decrypted is in some way unreasonable is absurd.
------------------------------
Subject: Re: Another sci.crypt Cipher
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 29 May 2000 03:14:45 -0700
In article <8gstfd$oud$[EMAIL PROTECTED]>, matthew_fisher@my-
deja.com wrote:
>....
>>
>> I believe the differential for 16 rounds will be 2^-60. A 2R
or 3R
>> attack could probably be mounted requiring 2^48 plain/cipher
text.
>>
>> R p1 p0
>> 0 0 c prob = 1
>> 1 c 0 2^-6
>> 2 c c 2^-6
>> 3 0 c 1
>> 4 c 0 2^-6
>> 5 c c 2^-6
>> 6 0 c 1
>> 7 c 0 2^-6
>> 8 c c 2^-6
>> 9 0 c 1
>> A c 0 2^-6
>> B c c 2^-6
>> C 0 c 1
>> D c 0 2^-6
>> E c c 2^-6
>> F 0 c 1
>> c 0 cipher text
>Tom,
>
>I have extended this attack via related keys. TC1 is
vulnerable to
>differential related key cryptanalysis. For best results the
attack
>requires chosen plain text.
>
>The attack requires a related key query. Basically, I want to
two keys
>that have only a difference in the 0 word with the XOR being
0x00 00 00
>0c
>
>The attack requires some text be run under one key, and some
text be
>run under the related key.
>
>The key schedule is
>
>0,1,2,3, 1,0,3,2, 2,3,1,0, 3,2,0,1
>
>Now since the attack can chose the plain text, the input will
always be
>equal to 0x00 00 00 0c thus offseting the difference in the
first round.
>With such a situation, the attack will have equal input to the
fifth
>round i.e. differential 0x00 00 00 00.
>
>K R p1 p0
> c 0 plain text
>0 0 0 0 prob = 1, Since key 0 differential is 0xc
>1 1 0 0 1
>2 2 0 0 1
>3 3 0 0 1
>1 4 0 0 1
>0 5 c 0 2^-6 the 0 key introduces a difference
>3 6 c 0 2^-6 the key difference does not carry forward
>2 7 c c 2^-6
>2 8 0 c 1
>3 9 c 0 2^-6
>1 A c c 2^-6
>0 B c c 2^-6 the difference is caused by the key difference
>3 C 0 0 1
>2 D 0 0 1
>0 E c 0 2^-6 the zero key cancels the difference
>1 F c 0 1
> x c assume the differential held if p0 = c
>
>The full differential has a 2^-42 chance. A 2R attack has a
chance of
>2^36, now we are getting somewhere! The attack is similar to
the
>differential related key attack on GOST proposed by Wagner,
Scheiner,
>et al.
>
>The full attack would need one related key query and around
2^36 texts.
>The counting requirements would run up the RAM to 2^32 or so.
>
>I noticed you have modified the cipher from the original so
this attack
>may no longer be valid. The addition of round counters will be
>irrelevant to this attack.
>
>This is a great cipher for study. Not to hard, not to easy,
just right.
That certainly is the best attack on TC1 so far. Ya the cipher
was designed to be conceptually easy so analysis would be easier.
In TC1a (which I will document later) I will change the key
schedule slightly to avoid these weak keys, and also optimize
the bit permutation against linear and differential
cryptanalysis.
I am trying to visualize how to program the search...
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Refs to "Hillclimbing" and other algorithms?
Date: Mon, 29 May 2000 10:07:21 GMT
>
> > Where can I find URLs and sample-code which refer to "Hillclimbing"
and
> > other computer techniques relevant to cryptanalysis?
> >
> > (I presume that many of them exist by now.)
>
> I don't have that impression. Hillclimbing in cryptanalysis appears to
> be a method due to Jim Gillogry. He explained a little bit of it in
our
> group but not to the extent for the uninitiated to be able to practice
> that method in my humble opinion.
>
> M. K. Shen
>
Hill climbing is used in lots of places, one particular place is in
neural networks for training. I would recomend looking on the web for
texts that explain the back propagation method for training neural
networks. Although I cannot see for the life of me why anyone would
consider using if for crypto analysis. I would be very interseted to
found out more on how it could be used.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Dan Kaminsky" <[EMAIL PROTECTED]>
Subject: Re: On dynamic random selection of encryption algorithms
Date: Mon, 29 May 2000 03:18:03 -0700
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> I should very much appreciate obtaining critiques and
> comments on the following (essentially simple) ideas:
>
> Let there be a set of n block ciphers that are deemed
> appropriate for being used in multiple encryptions with
> m constituent ciphers (m1 <= m <= m2). Let a PRNG be
> chosen by the communication partners and a secret session
> key be given. We'll use the key as the seed to the PRNG
> to generate pseudo-random number sequences required below.
>
> For each block of plaintext to be encrypted, first
> generate a random number m in [m1, m2]. Then randomly
> choose m algorithms from the available set of n
> algorithms. Subsequently perform a random permutation
> of the ordering of these to determine the sequential order
> with which the m algorithms are to be placed in the stack
> (eventually avoiding, if desired, the case that two
> consecutive algorithms in the stack are the same). Finally
> generate m keys that are required by these algoritms to do
> the encryption of the given block of plaintext.
Some thoughts:
Is your system more robust, in that a compromise of any given algorithm only
defeats blocks encoded with that algorithm when used in ECB mode, and only
defeats n/m messages when used in any form of chained mode? Or is it less
secure, since the increased complexity reduces the security of the total
message to that of the weakest algorithm?
In thinking about it, I believe I've come to the root of your problem, which
you try to avoid by specifying the generation of m keys for m ciphers: If
each cipher uses the same key, a compromise on *any* cipher will compromise
*every* cipher. So you get around this by having additional keying
material--essentially, more bits.
If I'm going to have more bits, it's generally presumable that it's more
secure to have those bits thoroughly mixed rather than segmented by
subcipher. Cracking one DES key does not grant you a third of a 3DES
encrypted message--for a reason!
Yours Truly,
Dan Kaminsky
------------------------------
From: Adrian Kennard <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Mon, 29 May 2000 11:36:32 +0100
David Boothroyd wrote:
>...
> I thought you said you were too young. The Poll Tax was replaced because
> Conservative MPs realised it was too unpopular. The idea that the police
> being able to demand that encrypted data (about which they have a reasonable
> suspicion) be decrypted is in some way unreasonable is absurd.
The idea that the police may have unfounded suspicion.
The idea that the individual may not wish to disclose a key
which can then be used to decode everything they have ever
recevied regardless of relevance, and sign things with their name, etc.
The idea that the data may not be encrypted, or the suspect
may not have the key and cannot prove this. After all, if plod
knew what it was then they would not need the key - they must have
only suspicions.
The idea that (a) if you dont have it then you can simply
say that - i.e. anyone gets off and the law is stupid, or (b)
that you have to somehow prove you dont have it, which is
just about impossible, and so anyone can easily be framed
by anybody else.
These "sting" operations are going to make it nice and easy for
people to be framed, I am sure. They are a way of pointing the
finger of suspicion at someone. Someone you can also send encrypted
data with suspect subject lines to, and who has no way to decode.
They end up with a record for not handing over a key and a stigma
that they only failed to do so to avoid more serious charges, when
in fact they did nothing.
The last point is one I had not considered before - if someone
does end up unfortunately unable to hand over a key - "people"
will assume they did so to hide something. They are assumed "guilty"
of a much worse offence by their peers with no real opportunity
to defend themselves. Nasty.
...
I cannot see it helping anything. For a criminal, if you are asked
to hand over a key that means that you know they dont have better
evidence - all the more reason not to incriminate yourself (basic
right, isn't it?)
Anyway, there are so many ways to hide encrypted data that it will
be pointless - surely.
--
_ Andrews & Arnold Ltd, 01344 400 000 http://aa.nu/
(_) _| _ . _ _ Professional Voice and Data Systems for Business.
( )(_|( |(_|| ) Gold Certified Alchemists, BT ISDN/ADSL Resellers
------------------------------
From: Boris Kolar <[EMAIL PROTECTED]>
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: Mon, 29 May 2000 11:56:03 +0200
David Blackman wrote:
> Scott Contini wrote:
> >
>
> > Here's my 2 cents:
> >
> > Factoring is certainly not NP-complete (though a proof of this
> > does not exist). We can factor in sub-exponential time, but the
> > fastest algorithms for solving general NP-complete problems take
> > exponential time.
> >
> > Scott
>
> I think there is a proof that if factoring is NP-complete, then either
> P=NP, or the extended Riemann hypothesis fails. I vaguely remember this
> is referenced in Garey and Johnson (but i've lost my copy). A lot of
> people would consider this to prove that factoring is not NP-complete,
> although technically it is not quite such a proof.
>
> It hinges on factoring being (almost certainly) in co-NP.
Factoring is in fact in the intersection of NP and co-NP. All problems that
are relevant to public-key cryptography are there.
The problem:
NP and co-NP =? P
is even more important, than P =? NP. It's widely believed, that the answer
is NO (the NO answer would also imply P /= NP).
Finding a problem, that is (NP and co-NP)-complete, would also be very
important for cryptography.
------------------------------
** 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
******************************
