Cryptography-Digest Digest #261, Volume #10 Sat, 18 Sep 99 01:13:04 EDT
Contents:
Re: SCOTT19U.ZIP_GUY/Questions Please ("Douglas A. Gwyn")
Re: Example of a one way function? (Paul Crowley)
Re: 3des? (Jerry Coffin)
Re: Exclusive Or (XOR) Knapsacks ("Douglas A. Gwyn")
Re: Okay "experts," how do you do it? ("Douglas A. Gwyn")
Re: Okay "experts," how do you do it? ("Douglas A. Gwyn")
Re: Second "_NSAKey" ("Douglas A. Gwyn")
Re: Exclusive Or (XOR) Knapsacks ("rosi")
Re: Okay "experts," how do you do it? ("Douglas A. Gwyn")
Re: ECC (again...) ("rosi")
Re: ECC (again...) ("rosi")
Re: Okay "experts," how do you do it? (jerome)
Re: 'noise' as a random source bleaching problems (Scott Nelson)
Re: 3des? ("Richard Parker")
Re: Ritter's paper ("rosi")
Re: Crypto 3.5
Re: Okay "experts," how do you do it?
Re: Crypto 3.5 (JPeschel)
Re: Okay "experts," how do you do it? ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: SCOTT19U.ZIP_GUY/Questions Please
Date: Sat, 18 Sep 1999 03:17:16 GMT
"Trevor Jackson, III" wrote:
> "fortified"? I think that's a media exaggeration.
Certainly part of the compound (underground bunker built around an old
school bus) was fortified. Remember, those people believed that some
day somebody like the government would come and try to annihilate them.
> The existence of missing audio tapes may be the rest of the
> evidentiary iceberg.
Maybe. Since among compound members only the "mole" (possibly) knew
that it was bugged, their supposedly private conversations ought to be
strong evidence as to whether they were victims or criminals. The
only audio tapes I heard were purported to show that the BDs were
preparing to set fire to themselves, but it sure didn't sound like it
to me.
Hm, we seem to have strayed completely off topic here.
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Example of a one way function?
Date: 17 Sep 1999 15:05:17 +0100
[EMAIL PROTECTED] (John Savard) writes:
> A simple example of a keyed one-way function - but not a trapdoor
> one-way function usable for public key encryption - would be this:
>
> f(x) = (x encrypted with DES) XOR x
>
> which is a keyed one-way function. It could be used in a hash
> function, or for generating things like session keys. But there is no
> known way to find x from f(x), even knowing the key.
Exhaustive search would be just about practical here, since x can only
take on 2^64 values.
A more commonly used keyed one-way function might be
SHA-1( KEY | x | KEY )
where | denotes concatenation.
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: 3des?
Date: Fri, 17 Sep 1999 21:05:53 -0600
In article <7ruhc0$15j$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (John Savard) wrote:
> > I remember a claim in AC that the key strength of DES with independent
> > keys is really only about 65 bits.
>
> Really? Hmm... have any refs for this fact? I want to look em up.
I believe you have AC2. Section 12.6 (page 295) says:
Although independent subkeys foil linear cryptanalysis,
this variant is susceptible to differential
cryptanalysis and can be broken with 2^61 chosen
plaintexts (see Table 12.15) [ 167,172]. It would seem
that any modification of the key schedule cannot make DES
much stronger.
IIRC, this attack was found by Biham and/or Shamir (like many
differential cryptanalysis attacks...)
Independent sub-keys takes 768 bits of key to get an effective key
size of approximately 65 bits or so. 3DES uses 112 bits of key to get
112 bits of effective key size -- even though 3DES uses three rounds
through the basic DES encryption (and decryption) engine, it needs
only two keys.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Exclusive Or (XOR) Knapsacks
Date: Sat, 18 Sep 1999 03:03:16 GMT
Gary wrote:
> What if the matrix wasn't square?
That's a different problem. Use SVD, which should work for GF(2)
so far as I can see at a first glance.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Okay "experts," how do you do it?
Date: Sat, 18 Sep 1999 02:45:36 GMT
Tom St Denis wrote:
> But most of the time it's easier to analyze a system if you know
> the guts.
You don't *need* to analyze it very much if you already know it.
> I could break a 20 year old system, but why?
In order to *learn* something of general applicability in a
relatively easy-to-understand context.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Okay "experts," how do you do it?
Date: Sat, 18 Sep 1999 02:38:02 GMT
> >It seems to me that we ought to be able to subject a cipher to an
> >objective test.
Patrick Juola wrote:
> It would be nice, yes. It would also be nice if we could automate
> the task of performing medical diagnosis -- after all, what makes
> a good diagnostician good? Knowledge of lots of different medical
> syndromes and their signs.
It's interesting that you chose that analogy. There is a very
interesting paper (still classified, alas) by Callimahos that
explores that analogy bewteen medical and cryptanalytical
diagnosis, side-by-side for many pages. Obviously, lots of
parallels can be drawn.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Second "_NSAKey"
Date: Sat, 18 Sep 1999 03:36:01 GMT
"Trevor Jackson, III" wrote:
> In "http://www.microsoft.com/security/bulletins/backdoor.asp"
> Microsoft(tm) claims that they have not given either key to anyone,
> particularly not the NSA. Thus, according to Microsoft(tm), the second
> key labeled _NSAKEY is purely a disaster prevention mechanism.
Thanks for the URL. Unfortunately, it doesn't really answer the
*obvious* questions: How could MS possibly "lose" the primary key
(yet retain the backup key)? We're talking about data here, that
can readily be copied and backed up in various physical locations,
including wherever they keep the "backup key". Also, what do they
mean by saying "The keys in question are the ones that allows us
to ensure compliance with the NSA's technical review."? Does that
mean exactly what I described in my previous posting (which was
based on a separate statement from Microsoft staff)? MS wouldn't
actually have to *hand over* the NSAkey to NSA for the "technical
review", but they would still want to use that key, not their
primary CSP-signing key, for the technical review process.
It was interesting to see that there is a third key in the test
versions of Win2K.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Exclusive Or (XOR) Knapsacks
Date: Fri, 17 Sep 1999 23:11:10 -0400
Dear Gary,
Thanks for the post.
1. Have to be sure if you were asking the 'complete' question or the
'incomplete'
one. I.e. When the problem is given, is it known for sure that X is a subset
sum?
Theoretically, the two are the same. However, in practice (or in
cryptographical
sense), they have a subtle difference IMHO.
2. About 'square'. It does not matter in a special sense. To be a bit
concrete,
to ask the 'complete' question (meaning X may or may not be a subset sum),
is NP-complete in the general sense if solution unique (complexity unknown
but 'the hardest', i.e. in terms of reducibility). If solution not unqiue
'in the true
sense', beyond NP-complete. (But not unique in the true sense, by the way,
is
useless to cryptography). To be concrete a bit more, if you are referring to
cryptographic properties, the 'non-square' fashion IS possible but need to
be in
such a way that you can invert (with the trapdoor information). As far as I
know,
there is no known way of solving this efficiently and the O(n^3) is just a
joke,
maybe a bad one. :)
I can be wrong.
My 0.2 cent if that can be picked up. :)
--- (My Signature)
P.S.
About 'It does not matter'. The characteristics or description (informal
here) of
the problem determines this. E.g. if the problem can have an equivalent
zero-one
set, lattice (spanned) is obviously a threat. In addition, if the solution
is unique
'under the attack model', "more than the bits" may not matter as much as one
wants (and this is, IMO, open question about density). Hope this makes
sense.
Sorry can't do any better. But thanks again for your post.
Gary wrote in message ...
>What if the matrix wasn't square?
>In particular if the number of elements were larger than the bit size.
>
>David Wagner wrote in message
><7rrgb0$7vd$[EMAIL PROTECTED]>...
>>In article <%_8E3.290$gE.6812@stones>, Gary <[EMAIL PROTECTED]> wrote:
>>> Problem:
>>> Given an n bit number X and a set {B1,B2,...,Bn} of n bit numbers;is
>there a
>>> subset whose elements collectively XORed give X?
>>>
>>> Can the general problem be solved easily?
>>
>>Yes. Gaussian elimination will solve it in O(n^3) time.
>
>
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Okay "experts," how do you do it?
Date: Sat, 18 Sep 1999 02:51:21 GMT
jerome wrote:
> an unknown designs a new cypher A and coppersmith, rivest and shamir
> design a another new cypher B. Will you read both papers with the
> same 'open mind' ?
If they're published in a reputable peer-reviewed journal, sure.
(The review/referee process is designed to ensure that only papers
of acceptable relevance and quality are published; often it involves
iterative editing until the criteria are met.) At least, I'd read
the title and abstract to see whether it might be worthwhile to
read further.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: ECC (again...)
Date: Fri, 17 Sep 1999 23:18:25 -0400
Jerry Coffin wrote in message ...
[snip]
>even if the symmetric algorithm is badly broken. At the same time,
>since you're encrypting only a VERY small amount of data with the slow
>public-key algorithm, there's little call to try to speed up the PK
^^^^^^^^
Perhaps (just a perhaps) one can call as much as one wants but to
not much avail.
--- (My Signature)
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: ECC (again...)
Date: Fri, 17 Sep 1999 23:20:34 -0400
Emmanuel Drouet wrote in message <[EMAIL PROTECTED]>...
>Hello !
>
>I'm looking for elliptic curves algorithms :
>a public key cryptosystem which doesn't derive from Diffie-hellman.
>
>The only algorithms I found are based on shared secret key and uses
>symetric cryptosystem (ECAES for example)...
>Why is it so difficult to find a public key cryptosystem which "simply"
No one really knows why, or if it is difficult at all.
>encode the text ?
>
>Could you help me ?
There is a slight chance that one day, somebody may help you.
--- (My Signature)
>
>Manu
>
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: Okay "experts," how do you do it?
Date: 18 Sep 1999 03:48:20 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 17 Sep 1999 17:25:39 -0700, Joseph Ashwood wrote:
>> he's paranoid but not totally wrong. just an example.
>> an unknown designs a new cypher A and coppersmith, rivest and shamir
>> design a another new cypher B. Will you read both papers with the
>> same 'open mind' ?
>
>I see no reason not to, one paper is likely to be very interesting, while
>the other is likely to involve a large body of comedic work.
so you cryptanalyze all the cyphers described by beginners ?
i can easily write a feistel network which -seems- not too
bad in 2hours.
after that, how resistant it is... even against known attack, it is
another matter. to find out you have to crypanalyze it and try
at least the most common attacks (linear, differential, key realated).
my cypher will likely be very weak but to find out that, you have
to spend much more than 2 hours.
so either you have a lot of time, either you don't.
>> if yes, that's mean you read all the cypher descriptions posted sci.scrypt
>> and elsewhere and study them as much as you study any AES proposal.
>> in fact i hope you don't because it is obviously a waste of time.
>
>With an AES candidate it is unlikely to find a break no matter how much time
>one spends, however the cypher A is likely to be broken (or at least
>suspected) by the time the reading is finished.
im not that efficient even on a simple cypher :)
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: 'noise' as a random source bleaching problems
Reply-To: [EMAIL PROTECTED]
Date: Sat, 18 Sep 1999 04:05:30 GMT
On Fri, 17 Sep 1999 21:15:03 -0400, [EMAIL PROTECTED] (Guillaume
Filion) wrote:
>Hi all,
>
>I'd like to try to have noise as a random number source as described in
>Phrack (http://www.phrack.com/search.phtml?view&article=p54-5 ) but I'm
>having some problems compiling the code provied to bleach the input.
>Here's what I got:
>
>[gfk@gfk bleach]$ make all
>gcc -w -c md5/md5.c
>gcc -c sha/shs.c
>gcc -o sha_distill sha_distill.c shs.o
>sha_distill.c: In function `main':
>sha_distill.c:9: `stdin' undeclared (first use in this function)
>sha_distill.c:9: (Each undeclared identifier is reported only once
>sha_distill.c:9: for each function it appears in.)
>sha_distill.c:14: `stdout' undeclared (first use in this function)
>make: *** [all] Error 1
>
>I'm using RedHat Linux 6 (Kernel 2.2.5-22) on a i586 processor and using
>egcs-1.1.2-12 as the compiler.
>Anyone knows what I should do to make it compile?
>
Looks to me like you haven't included stdio.h.
Best guess, you've done a cut and paste from your browser and
it trimmed the angle braces around stdio.h ('<') thinking
it was an html tag. You might try "view; page source"
and cut and paste from that.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: 3des?
Date: Sat, 18 Sep 1999 03:42:54 GMT
[EMAIL PROTECTED] (Jerry Coffin) wrote:
> Independent sub-keys takes 768 bits of key to get an effective key
> size of approximately 65 bits or so.
I'm curious, where do you get the figure of 65 bits for the effective
key size of DES with independent subkeys? Wouldn't a differential
cryptanalysis attack requiring 2^61 operations require the same number
of operations (on average) as a brute force attack against a key size
of 62 bits?
> 3DES uses 112 bits of key to get 112 bits of effective key size -- even
> though 3DES uses three rounds through the basic DES encryption (and
> decryption) engine, it needs only two keys.
Actually 3DES uses three 56 bit keys (168 bits) to get an effective
key size of 112 bits. 3DES with two keys can be attacked with a
meet-in-the-middle attack that requires (2^120)/n operations with n
known plaintexts. If n is greater than 256 then 3DES with two keys is
weaker than 3DES with three keys.
-Richard
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Ritter's paper
Date: Fri, 17 Sep 1999 23:44:00 -0400
Trevor Jackson, III wrote in message <[EMAIL PROTECTED]>...
[SNIP]
>Usually this means as secure/hard as X where X is "thought to be secure"
>or "thought to be hard". Hardly a convincing manner of proof.
>
Thought I alone had the semantics problem. Long live 'provably secure'!
(Even) As hard as???
(Can't help kidding a bit. :)
Thanks Trevor.
--- (My Signature)
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Crypto 3.5
Date: 18 Sep 99 03:36:37 GMT
JPeschel ([EMAIL PROTECTED]) wrote:
: Crypto 3.5
: (http://www.execpc.com/~sbd/Crypto.html)
: How secure do you reckon it is?
: :-)
I didn't see any obvious indications that it was snake oil; it used
Blowfish, which is secure. However, I see there is now another thread
about it having been cracked. What subtle indications did you pick up on?
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Okay "experts," how do you do it?
Date: 18 Sep 99 03:41:33 GMT
David Wagner ([EMAIL PROTECTED]) wrote:
: In article <[EMAIL PROTECTED]>,
: Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
: > I think he's complaining about the other side of the coin. The one where lack
: > of practical attacks is taken as an indicator that the cipher is secure. That
: > is not a scientific process.
: I'm lost: What does this have to do with the definition of "expert"?
: After all, the lack of published attacks in the open literature is an
: objective fact that doesn't depend on who you choose to call "expert".
I think one of my posts addresses this.
The existence of an attack is an objective fact.
Yes, so is the non-existence of one, but what is subjective, and depends
on who are considered "experts" is this: based on who _tried_ to attack
the cipher, what can we conclude about its security?
Surely an unbroken cipher closely examined by experts is more likely to be
secure than an unbroken cipher only a few amateurs have glanced at. That
is where this comes in.
John Savard
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Crypto 3.5
Date: 18 Sep 1999 04:34:08 GMT
[EMAIL PROTECTED] () writes:
>I didn't see any obvious indications that it was snake oil; it used
>Blowfish, which is secure. However, I see there is now another thread
>about it having been cracked. What subtle indications did you pick up on?
John, the work is not mine but Casimir's. Casimir enjoys hunting for
and breaking snake-oil. A while ago, he cracked a program called
"Keeper." Apparently the Keeper vendor later asked Casimir to
review Braun's Crypto 3.5. As Casimir puts it: "They were planning
to license from him, but I dissuaded them from doing so {:-) "
For some reason Braun also included a file called "crackme," in Crypto
3.5 and that may have persuaded Casimir to do so.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Okay "experts," how do you do it?
Date: Sat, 18 Sep 1999 02:43:33 GMT
Jeff Williams wrote:
> ... Having a newbie attempt to design a secure
> *system* early on as a learning exercise and then having an expert
> show him/her the gaping holes in the system they just designed might
> serve as a serious wake-up call. I know that books and instructors
> can tell you that a system is more than just a good algorithm, but
> designing a system and having the gaps exposed might be more
> instructive.
Unfortunately, that could involve a lot of work by a skilled
specialist, which makes it uneconomic. Suppose the Newbie
devises a piece-of-junk cryptosystem that is so baroque that
it actually takes a lot of work to make the first "break"
into the system, although thereafter it is an open book.
(Sometimes the Newbie simply concatenates a lot of easy
subsystems together.)
It's better economics to make the Newbie do most of the work..
------------------------------
** 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
******************************
