Cryptography-Digest Digest #268, Volume #14 Mon, 30 Apr 01 08:13:01 EDT
Contents:
Re: A Question Regarding Backdoors ("Panu H�m�l�inen")
Re: Key scheduling of block cipher (Ulrich Kuehn)
Re: impossible differentials (help please) (Ulrich Kuehn)
Re: A Question Regarding Backdoors ("Tom St Denis")
Re: A Question Regarding Backdoors ("Brian Gladman")
Re: impossible differentials (help please) ("Tom St Denis")
Re: A keen symmetric cipher idea ("Tom St Denis")
Re: A Question Regarding Backdoors (Leonard R. Budney)
Re: A Question Regarding Backdoors (Daniel)
Re: A Question Regarding Backdoors ("Tom St Denis")
Re: A Question Regarding Backdoors ("Tom St Denis")
Re: A Question Regarding Backdoors (Leonard R. Budney)
Re: DES source-code from Applied Cryptography (Richard Outerbridge)
Re: A Question Regarding Backdoors ("Tom St Denis")
----------------------------------------------------------------------------
From: "Panu H�m�l�inen" <panuh[@]cs.tut.fi>
Subject: Re: A Question Regarding Backdoors
Date: Mon, 30 Apr 2001 11:21:28 +0300
Knowing the encryption key is a backdoor. ;)
-- Panu
"Arturo" <aquiranNO$[EMAIL PROTECTED]> wrote in message
>
> AES candidates have been scrutinized and are open for everybody to see,
> so I doublt Rijndael could have any backdoor without anybody realizing it.
I
> certainly don�t think that a backdoor was included in AES requirements.
------------------------------
From: Ulrich Kuehn <[EMAIL PROTECTED]>
Subject: Re: Key scheduling of block cipher
Date: Mon, 30 Apr 2001 11:39:46 +0200
Reply-To: [EMAIL PROTECTED]
Mok-Kong Shen wrote:
>
> I like to re-raise an issue that I mentioned in a discussion
> of a thread of the group quite a time back.
>
> A block cipher commonly employs for its n rounds n subkeys
> that are derived from a user supplied key in some manner.
> One can apparently do simple modifications in two ways:
> (1) change the order of the subkeys for the rounds, (2) xor
> the subkeys with some secret random bit sequences. (These
> modifications could be altered independent of the change
> of the proper keys.)
>
Something similar to the second option was suggested for the IDEA key
schedule to avoid certain weak keys (Joan Daemen, Rene Govaerts, Joos
Vandewalle. Weak Keys for IDEA. Crypto 93). But this was suggested after
a carefull analysis of what yielded the weak keys in order to avoid
them. Although this is not exactly what you proposed, it sheds some
light on this kind of change.
For the order of the round keys you should read David Wagner, Alex
Biryukov. Advanced Slide Attacks. Eurocrypt 2000. There is an
explanation given for the twist in GOST's key scheduling. If you leave
it out, the cipher would be much more susceptable for slide attacks.
Hope this helps,
Ulrich
> Are there any negative impacts of such modifications to
> the security of the cipher? It seems that at least brute-
> forcing is rendered more difficult thereby.
>
> M. K. Shen
> -------------------------
> http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Ulrich Kuehn <[EMAIL PROTECTED]>
Subject: Re: impossible differentials (help please)
Date: Mon, 30 Apr 2001 11:49:14 +0200
Reply-To: [EMAIL PROTECTED]
Tom St Denis wrote:
>
> Could someone just explain the jist of the style of attack.
>
> I am hung up on if we take the difference of the round function output, or
> do we fully decrypt the last round and look for the impossible diff?
I would say that depends. In its basic form this attack decrypts the
data by one round. Consider a feistel network with bijective round
function as an example. There is a generic impossible differential
(0, a) -/-> (0, a) after 5 rounds (before the swap). This differential
is described in Knudsen's paper on DEAL.
In order to attack 6 rounds, you are looking for pairs that have input
diff (0, a) and output xor (a, b) (leaving out a possble final swap).
Then you look for keys of the last round that yield output xor b from
the inputs with xor a. Throw away all those keys. Finally only the
correct key remains, as it never suggests the impossible differential to
hold.
Of course, there might be, depending on the cipher, ways to optimise
such an attack in order to no have to guess all the key bits, attack
more than one round at the end, or attack the first round etc.
Hope this helps,
Ulrich
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Mon, 30 Apr 2001 10:37:09 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
"Chad Hogan" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> > > Could someone please give me an informed reply? I get nervous
> > > easily and don't want my door being broken in by overzealous
> > > Bush-Troopers.
> >
> > Ok I know you live in the states and think you are the only
> > people in the world.
> >
> > Rijndael WAS NOT MADE BY AMERICANS.
>
> Thanks for the public-service announcement, Tom. Rather than
> looking for a snooty reply, however, Bob was asking a simple
> question regarding back doors in cryptographic software as (may be)
> required by American law.
>
> Bob, perhaps you'll get some answers to your questions by looking
> at a few sites describing ITAR. ITAR talks about export, which
> doesn't seem to be exactly what you're looking for, but it might
> give you a starting point that will lead to your answers. Bill
> Unruh has an interesting cryptography page at
> http://axion.physics.ubc.ca/crypt.html which
> includes pointers to ITAR and other legal information.
Why would the **US** ITAR have anything todo witht the validitity of
a Belgium block cipher? Seriously, you would be looking at the
Belgiums if you really are paranoid.
Tom
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>
Comment: Key at: http://tomstdenis.home.dhs.org/key.asc
iQA/AwUBOu1AVQULrT+pXe8cEQIT0gCgn/pSZMovfnB/KjpPPoBl2e+p62kAn34S
qWjKAav9E5xpZC4G7rc/T3Ep
=mY2h
=====END PGP SIGNATURE=====
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Mon, 30 Apr 2001 11:44:08 +0100
"bob" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I am dabbling with my own flavor of an encrypted email client utilizing
> Rijndael 256-bit. I live in the States and am concerned about whether or
> not a backdoor is needed or mandated by the govt.
>
> Could someone please give me an informed reply? I get nervous easily and
> don't want my door being broken in by overzealous Bush-Troopers.
This is a complex subject and not one on which to seek amateur advice. I am
not a Lawyer so you will need to take the following only as my informal
understanding of the situation. Please do not rely on what I say!
If you build an AES based cryptographic capability there are a number of
levels at which backdoors have to be considered but I will cover only two
here - any in the AES algorithm itself and any that you are asked to
implement in your product.
Taking the AES algorithm first, it is possible that this has a weakness that
is not openly known but is known to an organisation such as NSA. If such a
weakness exists, you will not know about it and will not be 'asked' to
implement it since you are already doing so simply by using Rijndael (AES).
So you really don't need to worry about this.
Turning to any backdoors you need to put into your product, as far as I am
aware, if you build and deploy a cryptographic product that you will not
export from the US, you do not have to seek any US government approval for
the product and do not have to build in any weaknesses or backdoors.
However, if you wish to sell the product to a US government agency, you will
need to obtain approval that is is good enough for this purpose and this may
involve product changes that will not necessarily be explained to you. And
a condition of being able to sell to the US government may be that you
modify your commercial product in some way as well. This is not a legal
requirement but is simply a way that some governments (and maybe the US
government) use to maintain background control over domestic cryptographic
products. You are in the best position here if you can afford not to deal
with the US government since in this case, as far as I know, there are no
constraints on what you can sell within the US domestic market.
However, if you wish to export the product outside the US, there are export
controls on cryptography and hence you may in some circumstances need to
obtain an export license. In the main, the extent of the changes that you
need to make and the possibility that you will be asked to implement a
backdoor depend on what sort of product you wish to export and where you
wish to export it to. You really need to look up the BXA regulations here
since they are very detailed.
In outline, a software product that is public domain source code is not
export controlled but you have to inform BXA about its existence if it might
be exported from the US (e.g made available on a web site). You won't have
to add any backdoors here.
A retail product - a commodity product sold in shops without extensive
customer support - can be exported after a simple review by BXA to all but a
small number of 'rogue' nations. You won't have to add backdoors here
either.
Hardware and high quality software based cryptographic products that are
exported to customers outside the US and which require significant technical
support (i.e custom designed and non retail products) are subject to export
controls and you may either be refused an export license or be asked to
modify the product in order to obtain one depending on the nature of the
product and the intended client(s).
I hope this helps but I emphasise, again, that this is only my understanding
of the situation and may well be (in fact is quite likely to be) wrong in
some of the details. In particular, you should seek the advice of a lawyer
before you export a cryptographic product from the US since it is one of the
few nations that actually seeks to enforce its controls.
Brian Gladman
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: impossible differentials (help please)
Date: Mon, 30 Apr 2001 10:39:23 GMT
"Ulrich Kuehn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > Could someone just explain the jist of the style of attack.
> >
> > I am hung up on if we take the difference of the round function output,
or
> > do we fully decrypt the last round and look for the impossible diff?
>
> I would say that depends. In its basic form this attack decrypts the
> data by one round. Consider a feistel network with bijective round
> function as an example. There is a generic impossible differential
> (0, a) -/-> (0, a) after 5 rounds (before the swap). This differential
> is described in Knudsen's paper on DEAL.
>
> In order to attack 6 rounds, you are looking for pairs that have input
> diff (0, a) and output xor (a, b) (leaving out a possble final swap).
> Then you look for keys of the last round that yield output xor b from
> the inputs with xor a. Throw away all those keys. Finally only the
> correct key remains, as it never suggests the impossible differential to
> hold.
>
> Of course, there might be, depending on the cipher, ways to optimise
> such an attack in order to no have to guess all the key bits, attack
> more than one round at the end, or attack the first round etc.
This does help :-)
Is it not possible that the incorrect keys will not be thrown away too?
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A keen symmetric cipher idea
Date: Mon, 30 Apr 2001 10:54:06 GMT
"David Wagner" <[EMAIL PROTECTED]> wrote in message
news:9cj24j$m4f$[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >1. Both users pick two large primes p and q, then form N = pq
> >2. To encode a message you take 0 < M < N and do, c1 = M mod p, c2 =
> >M mod q
>
> This is utterly silly.
>
> p divides M - c1, so if you have two known plaintexts (M,(c1,c2)),
> (M',(c1',c2')), then you can recover p as gcd(M - c1, M' - c1').
>
> You might want to study a bit more number theory before proposing any
> more such ciphers.
I agree. However my Koblitz book has not arrived and my "Dover Series"
number theory books don't cover much of this type of math.
I was just trying to spur discussion I wasn't trying to replace AES or
something ... geez.
Tom
------------------------------
Subject: Re: A Question Regarding Backdoors
From: [EMAIL PROTECTED] (Leonard R. Budney)
Date: 30 Apr 2001 07:01:54 -0400
"Tom St Denis" <[EMAIL PROTECTED]> writes:
> > > Rijndael WAS NOT MADE BY AMERICANS.
>
> Why would the **US** ITAR have anything todo witht the validitity of
> a Belgium block cipher?
If you're going to be so snooty--and you are--learn to read. He didn't
ask about the validity of the cipher. He lives in the US. He wants to
implement the cipher. He doesn't want to go to jail. So he asked a
sensible question on this list. If you don't know the answer, shut yer
cakehole.
Len.
--
Frugal Tip #35:
Don't be afraid to pay extra for quality bungee jumping equipment. In
the long run, you'll save!
------------------------------
From: Daniel <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Mon, 30 Apr 2001 13:07:06 +0200
On Mon, 30 Apr 2001 02:20:21 GMT, [EMAIL PROTECTED] (bob) wrote:
>I am dabbling with my own flavor of an encrypted email client utilizing
>Rijndael 256-bit. I live in the States and am concerned about whether or
>not a backdoor is needed or mandated by the govt.
>
>Could someone please give me an informed reply? I get nervous easily and
>don't want my door being broken in by overzealous Bush-Troopers.
>
>Thank You
Here are a few interesting links:
http://csrc.nist.gov/encryption/aes/
http://www.esat.kuleuven.ac.be/~rijmen/rijndael/
http://24.11.32.186/www.rijndael.com/index.html
http://www.vum.be/nbcomp354.html local newspaper article (in Dutch)
http://www.linuxsecurity.com/feature_stories/interview-aes.html
In an another article in our local newspapers the two guys who wrote
Rijndael claim there is no backdoor (they know of).
And thanks, Tom, Rijndael indeed is Belgian and tastes as good as
their chocolate or their beers or their cheeses! Couldn't resist but
here it is anyway http://www.belgium.com/ for more info on the last
topic :-)
best regards,
Daniel
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Mon, 30 Apr 2001 11:11:33 GMT
"Leonard R. Budney" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> writes:
> > > > Rijndael WAS NOT MADE BY AMERICANS.
> >
> > Why would the **US** ITAR have anything todo witht the validitity of
> > a Belgium block cipher?
>
> If you're going to be so snooty--and you are--learn to read. He didn't
> ask about the validity of the cipher. He lives in the US. He wants to
> implement the cipher. He doesn't want to go to jail. So he asked a
> sensible question on this list. If you don't know the answer, shut yer
> cakehole.
Then he should ask the right question which is "Is it legal to use 256-bit
symmetric keys in the US". This has nothing todo with AES or possible
backdoors.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Mon, 30 Apr 2001 11:13:03 GMT
"Daniel" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Mon, 30 Apr 2001 02:20:21 GMT, [EMAIL PROTECTED] (bob) wrote:
>
> >I am dabbling with my own flavor of an encrypted email client utilizing
> >Rijndael 256-bit. I live in the States and am concerned about whether or
> >not a backdoor is needed or mandated by the govt.
> >
> >Could someone please give me an informed reply? I get nervous easily and
> >don't want my door being broken in by overzealous Bush-Troopers.
> >
> >Thank You
>
>
> Here are a few interesting links:
> http://csrc.nist.gov/encryption/aes/
> http://www.esat.kuleuven.ac.be/~rijmen/rijndael/
> http://24.11.32.186/www.rijndael.com/index.html
> http://www.vum.be/nbcomp354.html local newspaper article (in Dutch)
> http://www.linuxsecurity.com/feature_stories/interview-aes.html
>
> In an another article in our local newspapers the two guys who wrote
> Rijndael claim there is no backdoor (they know of).
Sure sure, they probally had the NSA camp over at their labs while they made
it. The people are foolish enough to think that AES would be an open
process... muahahahahahahhaha (j/k)
>
> And thanks, Tom, Rijndael indeed is Belgian and tastes as good as
> their chocolate or their beers or their cheeses! Couldn't resist but
> here it is anyway http://www.belgium.com/ for more info on the last
> topic :-)
You guys got good beer? I thought canada was the home of good beer... (I
dunno I just turned the age of majority and don't drink...)
Tom
------------------------------
Subject: Re: A Question Regarding Backdoors
From: [EMAIL PROTECTED] (Leonard R. Budney)
Date: 30 Apr 2001 07:45:52 -0400
"Tom St Denis" <[EMAIL PROTECTED]> writes:
>
> Then he should ask the right question which is "Is it legal to use 256-bit
> symmetric keys in the US". This has nothing todo with AES or possible
> backdoors.
That's why you need to learn to read. He didn't ask whether Rijndahl *has*
backdoors, he asked whether he would be required to *put* backdoors in
a US-made implementation.
Len.
--
But most of the bugs are stupid little mistakes. BIND sometimes sends
SIGTERM to the wrong place, accidentally killing itself.
-- Dan Bernstein
------------------------------
From: Richard Outerbridge <[EMAIL PROTECTED]>
Subject: Re: DES source-code from Applied Cryptography
Date: Mon, 30 Apr 2001 08:01:45 -0400
In article <9cbfha$jj9$[EMAIL PROTECTED]>,
"Brendan Lynskey" <[EMAIL PROTECTED]> wrote:
> The above code includes a function called 'cookey'. Anyone know the purpose
> of this? I can't see anything similar in the algorithm. Is this an
> alternative way to do the Expansion Permutation?
cookey() performs a 1-bit right-rotate of the key in order
to pre-allign it with the data blocks (which are also right
rotated by 1-bit by the time they finish the IP), and splits off
the four 6-bit chunks used with the odd-numbered S-boxes into
one unsigned long, and the 6-bit chunks used for the even-numbered
S-boxes into another. The S-boxes themselves are also right-rotated;
this save us one of the bit rotations within the inner loop that
would otherwise have been needed in order to elide the E-perm.
outer
--
<[EMAIL PROTECTED]> :
Just an eccentric soul "with a curiosity for the bizarre".
Payloads to: A902/MCE307/3/17TPU-28413618 (or thereabouts)
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Mon, 30 Apr 2001 12:09:56 GMT
"Leonard R. Budney" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> writes:
> >
> > Then he should ask the right question which is "Is it legal to use
256-bit
> > symmetric keys in the US". This has nothing todo with AES or possible
> > backdoors.
>
> That's why you need to learn to read. He didn't ask whether Rijndahl *has*
> backdoors, he asked whether he would be required to *put* backdoors in
> a US-made implementation.
Oh gotcha. What form of a backdoor would he *want* to put in there? The
whole point of AES was to make a new more secure cipher that is std.
Whywould they want to compromise it?
Tom
------------------------------
** 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
******************************
