Cryptography-Digest Digest #460, Volume #13 Fri, 12 Jan 01 11:13:00 EST
Contents:
Re: Linear analysis (Tom St Denis)
Re: Differential Analysis (Tom St Denis)
16bit collision resistance hash function? ("[Basic]")
Re: 16bit collision resistance hash function? (Thomas Pornin)
Re: Help.......Choice of Rijndael as the AES (Dido Sevilla)
Re: Another Enigma Emulator ([EMAIL PROTECTED])
Re: 16bit collision resistance hash function? (Dido Sevilla)
Re: NSA and Linux Security (digiboy | marcus)
Re: NSA and Linux Security (digiboy | marcus)
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: NSA and Linux Security ([EMAIL PROTECTED])
Different DES ([EMAIL PROTECTED])
Re: Comparison of ECDLP vs. DLP (Bob Silverman)
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: Comparison of ECDLP vs. DLP (David Wagner)
Re: 16bit collision resistance hash function? ("[Basic]")
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Linear analysis
Date: Fri, 12 Jan 2001 13:05:16 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> I thought it was (2/p)^r, not 1/(p^2)? How do I go from knowing about
> the Walsh Transform of a function, to knowing how many rounds are needed
> to make the cipher secure against linear attacks?
Oops... it is infact P = p^(-2) (P = required plaintexts). 2/p is from
differential analysis.
> > In other words if you used the sbox as an 8-bit cipher it would be
> > immune to differential attacks after two rounds (given by
> > (2/(4/256))^r > 256) and a single round for linear attacks.
>
> Well, I'm using the 8x8 sbox as the F function of a 16 bit fiestel. I
> think this means that I need
> (2/DP_max)^r > 65536
> to be secure against differential attacks. If DP_max is 4/256, this is:
> (2/(4/256))^r > 65536
> (2*(256/4))^r > 65536
> (2*64)^r > 65536
> 128^r > 65536
> and taking the log2 of both sides, this becomes:
> r log2(128) > log2(65536)
> Thus, using r > 16/7 should be sufficient to protect against
> differential attacks.
This is not true. A Feistel with only two rounds CANNOT be secure. You need
at least three rounds for the Luby-Rackoff condition of security. I would
use at least three or four rounds.
> But what do I need r to be to protect a 16 bit fiestel from LINEAR
> attacks? That's what I need to know.
Well if you are using the AES sbox this is (16/256)^-2 or 65536/256=256. So
after two rounds (256)(256) = 65536 you are set.
However, you can often bypass at least one round (It provable that in a
Feistel with a Bijective round function that in three rounds you must attack
at least two rounds, I did it in my TC5 paper :-)).
> > Keep in mind that the algebraic degree (sans the affine transform) is
> > low and can be manipulated with interpolation attacks (Knudsen has a
> > paper on the subject).
>
> Well, I'm considering using the AES sbox *with* the transform... or the
> TC5 sbox. Is the WalshTransform the same as the algebraic degree?
No. Unfortunately I am not well versed on Algebraic degree. However, you
should read Knudsens paper anyways.
> And how does it (either the WT, or the algebraic degree) help me perform
> (or help me prevent) a linear attack on the cipher?
Dunno.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Fri, 12 Jan 2001 13:08:53 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> The code is mostly similar, except where you have the line:
> ++table[x^y][sbox[x]^sbox[x^y]];
> I have something which is equivalent to:
> ++table[x][sbox[x]^sbox[x^y]];
Your second line here is still WRONG. You have to use [x^y] in the first
index. Otherwise the table is meaning less. The difference is not "x" or
"y" it's "x^y". I.e read the table as
table[inputdifference][outputdifference].
> I'm not quite certain why there should be a difference.
> Anyway... I now have changed to something resembling your code, and it
> strangely tells me that *all* differences (even 0->0) have probability
> 1/256 -- which is clearly wrong.
Yup should be wrong :-)
> Here's my new code:
> void probs(/*char* file,*/ unsigned char *sbox) {
> int x, y;
> FILE * f = /*fopen(file,"w")*/ stdout;
> unsigned int table[256][256] = {0};
> for( x = 0; x < 256; ++x )
> for( y = 0; y < 256; ++y )
> ++table[x^y][sbox[x]^sbox[x^y]];
> printf("Differences calculated\n");
> for( x = 0; x < 256; ++x )
> for( y = 0; y < 256; ++y ) {
> if( table[x][y] <= 1 ) continue;
> fprintf(f,"%02x->%02x ",x,y);
> fprintf(f,"(%d/256)\n",table[x][y]);
> }
> /*fclose(f);*/
> }
I would memset the table first. I dunno if = { 0 } will set all the
elements. Also this function should work...
> Any idea what I'm doing wrong, here?
Is the SBOX valid? Look at my sboxgen code if you need pointers.
> > > Here's my AES sbox generating code (copied verbatim):
> [snip]
> > > Is this correct or incorrect?
> > >
> > > I suppose that either the XOR pair, or the sbox generator, is wrong,
> > > but I don't know which, or how.
> >
> > The former is wrong.
>
> Good, I guess -- I was afraid that both might be wrong :)
Hehehehe
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "[Basic]" <[EMAIL PROTECTED]>
Subject: 16bit collision resistance hash function?
Date: Fri, 12 Jan 2001 14:43:34 +0100
Hi,
is there any way to produce a hash value that has only 16bit length but is
as collision resistance as possible? There is no other property needed than
a maximum of collision resistance.
ebfe
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: 16bit collision resistance hash function?
Date: 12 Jan 2001 14:00:21 GMT
According to [Basic] <[EMAIL PROTECTED]>:
> is there any way to produce a hash value that has only 16bit length but is
> as collision resistance as possible?
Oh, yes. Simply take MD5, and keep only the first 16 bits of the result.
You will get the maximum collision resistance possible, that is, one
will have to calculate on the average 256 hashes to have a reasonnable
chance of getting a collision.
--Thomas Pornin
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: Help.......Choice of Rijndael as the AES
Date: Fri, 12 Jan 2001 22:21:18 +0800
Haider Ali wrote:
<snip>
>
> I am working to see how the choice of Rijndael as the AES can be justified.
> Or if others were better in certain regards........
>
Read NIST's "Report on the Development of the Advanced Encryption
Standard (AES)" at
http://csrc.nist.gov/encryption/aes/round2/r2report.pdf. It's an
interesting read, mainly because NIST actually explains what went into
the selection process, and gave their reasons for their choice of
Rijndael as AES. I'm inclined to accept their justifications, mainly
because I had to choose an encryption algorithm for use with a project
I'm working with, and happened to choose the same AES round 2 finalist
that eventually got selected long before AES finally announced which
algorithm was chosen for many of the same reasons they did. However,
you'll find a lot of people on this list who would disagree with the AES
choice if you try looking in the newsgroup archives up to a couple of
weeks after October 2, 2000... Some of what they have to say is quite
instructive.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Another Enigma Emulator
Date: Fri, 12 Jan 2001 14:30:06 GMT
> It's really cool... and it works too! (Tested it on a previously
> encoded message of my own.)
Thanks! :o)
> What I'd like to know, though, is... how do you get a hold of these
> flash carts then?
>From www.lik-sang.com - look under products, back-up devices.
Paul
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: 16bit collision resistance hash function?
Date: Fri, 12 Jan 2001 22:30:21 +0800
"[Basic]" wrote:
>
> Hi,
>
> is there any way to produce a hash value that has only 16bit length but is
> as collision resistance as possible? There is no other property needed than
> a maximum of collision resistance.
>
No matter how you designed the algorithm, your hash function's collision
resistance would be laughably low. If you have 16 bits, then there are
only 65,536 possible hash values, and even an antique computer from the
late 1970's or early 1980's would have no trouble determining collisions
from your hypothetical hash function. You only have to find 64k messages
that produce each possible hash value, which is not at all difficult.
The reason why all hash functions currently in use are at least 128 bits
long, and in many cases much much longer, is precisely to prevent this
kind of brute force attack. The total number of hash values for Tiger
is 2^256 or 1.1579 x 10^77, which is about as many hash values as there
are sub-atomic particles in the visible universe, making it practically
impossible to find collisions in this brute force manner.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: digiboy | marcus <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 14:41:33 GMT
In article <93lttf$egr$[EMAIL PROTECTED]>,
Greggy <[EMAIL PROTECTED]> wrote:
> I don't remember the NSA bothering too much to explain the NSA key in
> Windows...
They didn't because they porbably didn't have anything to do with it.
What Bruce Schneier had to say about it:
http://www.counterpane.com/crypto-gram-
9909.html#NSAKeyinMicrosoftCryptoAPI
Basically what this typical self-paranoid US story came down to
was "Oh, there's some code that contains the letters 'nsakey' in it...
the NSA must be dropping trojans into Windows and being rather obvious
about it too!"
> Look, the bottom line is if they don't trust me with national security
> then neither do I trust them with national security.
Err.. but what do _you_ know about National Security compared to the
NSA? I'm not quite getting your angle, apart from the typical "arm
ourselves to the teeth in our Texan compounds before the NSA/FBI come
to invade us" type one.
> Sort of like if a politician doesn't trust me with a gun, I don't
> trust him with an office.
Again, most politicians (most) have spent quite a long time getting
qualified enough so that the majority of the voters will trust him with
an office. The arguement about freely arming is nonsensical in
comparison - does the majority of the people in your state have to vote
in your favour to allow you to buy a weapon? How extensive are
background checks when you buy a gun, if any? Are you constantly being
mositored/audited on your ownership of a gun, as compared to holding
office?
> It really is simple if you want to let go of your
> preconceived opinions and just think about it for a moment.
I dunno how to put this as eloquently as I really want, but it really
seems that you are the one isn't really thinking on a wider
perspective. Just the same ol' "Government is bad" bullshit that always
spews forth from the States. If you hate governments and monopolies so
much, all want to hold arms, feel for the rights of the 'people'
(including any criminals, terrorists, etc, etc), why not become a pure
Communist state and all join the fucking army? Yeah, ironic.
Anyway, my main point I was going to relate was this: If you did not
have a NSA _then_ you would notice the difference. See how many more
people would die, how much higher crime would rise, how many more
corrupt politicians could get away with it, etc etc etc etc etc etc etc
etc. Unless you're big on anarchy this would obviously be pretty bad.
--
[ marcus ] [ http://www.cybergoth.cjb.net ]
[ ---- http://www.ninjakitten.net/digiboy ]
[ The only people up in arms about ]
[ personal privacy are those with ]
[ something to hide. ]
Sent via Deja.com
http://www.deja.com/
------------------------------
From: digiboy | marcus <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 14:55:54 GMT
In article <93lt75$dvv$[EMAIL PROTECTED]>,
Greggy <[EMAIL PROTECTED]> wrote:
> You have an unrealistic view of how any government works, let alone
> America's. The government is corrupt and the people are sheep.
The intelligence agencies are still accountable to the government.
Granted they have full access to do basically _whatever_ is required to
accomplish their goals, but they must still report and be accountable.
> > The government of the USA pays for the NSA,...
>
> So you know who they work for. That is a step in the right direction.
...and the government of the USA is acting in the best interests of the
citizens of the USA.
> What the hell do you mean, "What about it?" You sound like violating
> the privacy of citizens is fine with you!!!
Well, it's certainly fine with me. The auto-scanning of my e-mails,
phone calls, SMS messages, whatever, etc. from, say, Menwith Hill,
isn't going to provide my government (or the overbearing US one) with
any interesting titbits of valuable information.
> > Echelon is designed to catch the stupid criminal who thinks e-mail
> > is secure & safe.
>
> I don't believe you are naive to believe that lame excuse.
It's true though. Put it this way, do you think that someone is sitting
at a desk somewhere actively listening to the phone calls of every
citizen or reading every email? If so, you must lead a happy life -
only willing to talk to people on the street in encrypted language in
case Big Brother is watching, etc. and encrypting every single email,
SMS message, etc etc using one-time pads. Oh wait, these posts aren't
encrypted are they? We've given them free info! Argh! Eeek!
> That's like
> the one, "The truth about JFK's assassination must be kept from the
> people of America for national security reasons."
Elvis is still alive too... *rolls eyes* If JFKs assassination was by
the US government as 'everyone who's seen the film'� will believe
there's quite a lot of supporting rumours in their favour of a need to
eliminate a threat to national security.
> > But of course, because the 'criminal' actions are covered up you
> > have no evidence to back up these claims.
>
> Oh, come on! You aren't that naive!
What's naive? How can the average joe on the street have any
substantial evidence that would hold up in court against the NSA?
National security, as a case, would win regardless.
--
[ marcus ] [ http://www.cybergoth.cjb.net ]
[ ---- http://www.ninjakitten.net/digiboy ]
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 12 Jan 2001 15:15:21 GMT
Subject: Re: Comparison of ECDLP vs. DLP
David Wagner wrote:
DJohn37050 wrote:
>With ECC, I can validate for a candidate public key
>that a private key logically exists.
Yeah, but why would you want to? What threat does this protect against?
But, if for some reason you need to verify this property, it is trivial
to do, no matter what cryptosystem you use: just verify that the key-owner
can sign a random challenge."
This is a common misconception. Signing a random challenge shows active POP,
proof of possession. It does not show the public key is valid, that is PKV. I
can own a private key that works with an invalid public key. This is easy to
show, as an invalid public key may be easy for anyone to break, that is, not
represent a hard problem. POP and PKV show different things, both have their
uses.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 12 Jan 2001 15:26:07 GMT
Subject: Re: Comparison of ECDLP vs. DLP
David Wagner wrote:
"
DJohn37050 wrote:
>So not only is RSA more likely to have an error in key gen, it is also more
>difficult to test to see if there WAS an error. If I have a "bet-the-company"
>key, I really, really, really want to KNOW there was no error, such as the
>Intel HW bug, or a SW bug, etc.
In that case, it seems that you will want El Gamal, not ECC or RSA.
El Gamal keys are even easier to verify than either ECC or RSA."
I think by El Gamal you really mean normal discrete log keys, e.g., DSA/DH,
ElG, etc.
In this case I would say that anything DL keys can do, ECC keys can do better,
once the basic operation (modexp or point multiplication) exists. ECC does not
REQUIRE a random set of domain parms to thwart Gordon's attack concern (cooked
domain parms), as does DSA/DH. ECC keys and certs are much shorter. DSA/DH is
open to advances in both GNFS AND Pollard rho, ECC just to Pollard rho, that
is, DSA might weaken (on the field size p) but ECC not break, but if ECC in
general weakens, then (every expectation would be that) so does DSA (on the
subgroup size q).
Don Johnson
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 15:19:12 GMT
In article <93mfk8$5j0$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
> Just a note - if SHA-1 has some kind of secret backdoor which allows
us to find
> collisions easily, does this lead to key agreement? (i.e. do
chameleon hashes
> imply key agreement) (I have a sneaking suspicion that they imply
oblivious
> transfer)
>
the problem is not to find collisions. It has been shown that for the
160 bit SHA-1 hash, the likelihhod of finding a collision is extremely
rare, and beyond the realm of reasonable worry.
the problem is a different one, that of the hash *leaking* the secret
key, if the hash algorithm is broken:
see the revised RFC2440:
http://www.imc.org/draft-ietf-openpgp-rfc2440bis
p.60
begin quote:
" * The DSA algorithm will work with any 160-bit hash, but it is
sensitive to the quality of the hash algorithm, if the hash
algorithm is broken, it can leak the secret key. The Digital
Signature Standard (DSS) specifies that DSA be used with SHA-1.
RIPEMD-160 is considered by many cryptographers to be as strong.
An implementation should take care which hash algorithms are
used with DSA, as a weak hash can not only allow a signature to
be forged, but could leak the secret key. These same
considerations about the quality of the hash algorithm apply to
Elgamal signatures."
end quote
but, this is a general problem in how the algorithm is
cryptographically implemented, and not really an *NSA* security issue.
perhaps people here more knowledgeable in the actual implementation
would care to comment,
vedaal
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED]
Subject: Different DES
Date: Fri, 12 Jan 2001 15:19:51 GMT
Hi,
I'm trying to write a DES encrypion routine and
have read 3 different explanation on DES. My
problem is that all this three explanations are
different from each other. Here are some examples.
1. Different S-boxes how can this be?
2. One uses a table called PC1 another don't.
3. One uses IP and IP^-1 the others don't.
Where can I find an official description of DES?
Regards,
Phyz
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Fri, 12 Jan 2001 15:33:15 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (DJohn37050) wrote:
> Bob Silverman said:
> It is clear that time/space issues can not be separated. Any
> algorithm can be broken in time O(1) if enough space for suitably
> large lookup tables is available."
>
> I would say that time is involved to BUILD
> the lookup table and that that TIME counts as part of the TIME cost
of the
> attack.
Don:
I respect you. I really do. But there are times when you make
pronouncements without being aware of existing research results.
One need not build an entire table of the possible outcomes in order
to have time/space tradeoffs. May I suggest you read the papers
of Shamir & Schroeppel (20th Ann Symp on Foundations of COmp. Sci),
Shamir & Birykov's attack on A5/1 (http://cryptcom.org/a5.ps)
and Hellman's classical paper "A cryptanalytic time-memory tradeoff"
IEEE Trans Inf Theory 1980 [there are many more such results]
These results show that there is an entire spectrum of time/space
tradoffs that are possible (especially Hellman's result). One
can go from O(1) space and exponential time to O(1) time and
exponential space or (almost) ANYTHING IN BETWEEN.
This is why I said that one can not ignore SPACE in considering
keysizes (yet which you continue to ignore). One can always trade
time for space.
Indeed, even in the Number Field Sieve, one could reduce the space to
something very tiny. Just make the factor base consist of 4 primes;
2 and 3 for the linear polynomial and the first two primes that
split in the extension for the higher degree polynomial. Of course,
you are going to compute for a VERY VERY long time before finding
4 instances of the polynomials which factor over this factor base.
(i.e. we are talking u^2u time where u ~ log(10^40)/log(3) ~= 10^320)
This is equivalent to a brute force search on a 1000 bit symmetric key.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 12 Jan 2001 15:39:38 GMT
Subject: Re: Comparison of ECDLP vs. DLP
Bill Unruh wrote:
"And where will you find 10^50 machines to carry out this parallel table
build? Any crypto system can be broken in O1 time is you use O(2^N)
machines. It is an emminantly parallelizable problem."
Yes, that is the point, symmetric keys and hashs (and ECC) can ALL be broken by
massive parallel machines. So you use a key size for ALL of them that is
consistent and ensures a bad guy cannot do it. This is a straightforward
calculation and so is not subject to much error, just double the bitsize of the
hash or ECC key as the symmtric key you are protecting. Then they will have a
consistent strength, no weakest link, all the links are equally weak or strong
(depending on how you look at it).
Now, what to do with RSA? RSA needs TIME and SPACE to break using GNFS. But
this involves conversion factors, somehow you must find a way to convert TIME
into SPACE (in effect), via a real world COST function. You can do that, with
the conversion assumptions, or you can just use TIME, which is being
conservative. The point being that the conversion assumptions MIGHT be shown
to be wrong in the future, if storage gets really cheap or there are
improvements to the GNFS algorithm to use less storage or both.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 12 Jan 2001 16:05:35 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
DJohn37050 wrote:
>David Wagner wrote:
>>DJohn37050 wrote:
>>>With ECC, I can validate for a candidate public key
>>>that a private key logically exists.
>>
>>Yeah, but why would you want to? What threat does this protect against?
>>
>>But, if for some reason you need to verify this property, it is trivial
>>to do, no matter what cryptosystem you use: just verify that the key-owner
>>can sign a random challenge."
>
>This is a common misconception. Signing a random challenge shows active POP,
>proof of possession. It does not show the public key is valid, that is PKV.
I don't understand. You said earlier that you want to be able to prove
that some private key exists. Being able to sign a random challenge proves
that some private key exists.
If you meant to talk about proving "validity" of the public key, and if
"validity" means something more than the mere existence of a private key,
could you tell me what you mean by "validity"?
Are you perhaps referring to the ANSI checks for weak keys? If so,
I must admit in advance that I will be underwhelmed by this so-called
`advantage'. The ability to check the public key for weak keys seems to
me to be such a second- or third-order concern for most real systems as to
not be a very important consideration in the choice of cryptosystems.
(By the way, in RSA it is also possible to validate the candidate
public key for weak keys: Just insist that the key generator issue a
non-interactive zero-knowledge proof of validity. It will be slower
and more complicated for RSA than for ECC, but it is possible.)
------------------------------
From: "[Basic]" <[EMAIL PROTECTED]>
Subject: Re: 16bit collision resistance hash function?
Date: Fri, 12 Jan 2001 16:55:41 +0100
thats exactly the problem. I only have 16bit to hash a single 64bit block. I
can not calculate md5 for rounds and rounds and store the first 16bit as the
maximum space for the hash value IS 16bit.
------------------------------
** 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
******************************
