Cryptography-Digest Digest #885, Volume #12 Tue, 10 Oct 00 03:13:01 EDT
Contents:
Re: A new paper claiming P=NP (Mike Oliver)
Re: Need help: considerations for IV and Keysetup (Benjamin Goldberg)
Hash idea. (Benjamin Goldberg)
Re: Authenticating a PIN Without Compromising the PIN (Benjamin Goldberg)
Re: Rijndael test vectors (Benjamin Goldberg)
Possible secure CRC using shrinking? (Benjamin Goldberg)
Re: No Comment from Bruce Schneier? (Benjamin Goldberg)
Looking for paper (Benjamin Goldberg)
Re: A new paper claiming P=NP (David Eppstein)
Re: Authenticating a PIN Without Compromising the PIN (David Schwartz)
working with huge numbers ("DeSilva")
Re: A new paper claiming P=NP (Mike Oliver)
Re: A new paper claiming P=NP (Nico Benschop)
Re: AES Runner ups (John Savard)
Re: Possible secure CRC using shrinking? ("Scott Fluhrer")
Re: A new paper claiming P=NP (Bill Unruh)
Re: Why trust root CAs ? ("Lyalc")
Re: On block encryption processing with intermediate permutations (Mok-Kong Shen)
Re: working with huge numbers (Mok-Kong Shen)
----------------------------------------------------------------------------
From: Mike Oliver <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Mon, 09 Oct 2000 22:19:55 -0700
Ross Smith wrote:
>
> Mark William Hopkins wrote:
>> Pshaw. Reviewing a proof is not difficult. That's P-time. FINDING the
>> proof, on the other hand, that's NP-time or worse. Since P is not equal to
>> NP, then reviewing is easier than finding.
>>
>> Therefore, it should be fairly easy to spot the flaw in the paper. No
>> demo programs are needed.
>
> Ah, but that "...or worse" gives them an out. If reviewing a proof is
> P-time, but *finding* the proof is *worse* than NP-time, then reviewing
> can still be easier than finding without contradicting P=NP.
At the risk of playing clueless straight man here, let me point
out that if validating a proof is P, then finding a proof is
ipso facto NP, since you can guess the proof and then check
if your guess is correct in P time.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Need help: considerations for IV and Keysetup
Date: Tue, 10 Oct 2000 05:39:00 GMT
[EMAIL PROTECTED] wrote:
[snip]
> A standard win32-gui application receives a password from the user and
> communicates with the kernel driver.
You *only* have a gui for activating the driver, no DOS version of the
program? What if someone wants to use it in a .bat?
[snip]
> Considerations:
> 1) Password Setup.
> I want to use the highest strength of the chosen Cipher, i.e. 256bit.
> How do I receive a 256bit key? I could generate 256bit pseudorandom
> bits, save them in a key file, and ask the user to hide that file well
> (e.g. on a floppy disk, steganography etc.).
Using psuedorandom bits is never a good idea for a cipher key, unless
they're generated by seeding a CSPRNG with the password... in which
case, you are, in effect, taking a hash of the password. Why not just
use a purpose built hash function in the first place?
> Or, I could receive a password from the user, and generate a hash. The
> problem is to receive a hash digest of size 256bit; I only know of
> Haval (where copyright issues are not really clear, and its strengh to
> me unknown) and a modified Ripemd (which strength is actually only
> that of the 128bit version).
Part of the problem with a password is that it has much less than 256
bits of entropy, unless you require it to be so. If you have an 8
character passphrase, a dictionary attack is possible. You need to
require that there be 256 bits of entropy in the passphrase to actually
have 256-bit security. To fulfill this requirement, we can't just ask
for 32 bytes... english text is highly structured/ordered, meaning 32
characters is actually much less than 256 bits. What I would suggest
doing, is use a really good compressor, like PPM, and compress the
user's passphrase, and require that the compressed passphrase be at
least 256 bits long to be considered valid.
To help the user know if his passphrase is long enough to be valid,
start with the "ok" button grayed out, and after each letter is typed,
do a trial compression, and if it's long enough, activate the button,
and if it's too short, deactivate the button. Also, showing the length
of the compressed passphrase will help.
To help the user avoid typos in such a long string, I would suggest that
you show the whitespace characters in the clear, and all other letters
masked as "*"s ... no masking at all would be Bad (the system could be
broken by watching over the user's shoulder), but if the user can't tell
where the spaces are, it's easy to unintentionally miss one, or add an
extra one. Showing the spaces doesn't lower security that much, I don't
believe, unless the passphrase was picked (verbatim) out of a book which
is available to the attacker -- then it might be possible for the
opponent to search for the pattern of spaces & lengths of the words.
> Yet I would prefer that all a user is required to do is to enter a
> password to access his scsi tapes. Should I use Haval? Or could I use
> something else. Like PKCS-5? I haven't looked at PKCS-5 yet, would
> love to hear some comments.
I would advise you get two hashes using two structurally different hash
algorithms (like SHA1 and RIPEMD), and take the first 256 bits from the
concatenation of the results. It makes no difference, security wise,
whether you use the compressed string or the original string.
Also, if you're wondering how someone could think up (and remember) 256
bits of entropy, simply suggest that they use some poetry. Most people
already know some poetry (from elementary or high school). Or a line or
two from a play or movie.
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Hash idea.
Date: Tue, 10 Oct 2000 05:39:10 GMT
Here is an idea for a hash function which outputs 128 bits. The mix()
function is from the ISAAC PRNG, and the shift constants were chosen so
that full avalanche would be achieved.
typedef struct { int32 a,b,c,d,e,f,g,h; } ctx;
#define mix(a,b,c,d,e,f,g,h) { \
a^=b<<11; d+=a; b+=c; b^=c>>2; e+=b; c+=d; \
c^=d<<8; f+=c; d+=e; d^=e>>16; g+=d; e+=f; \
e^=f<<10; h+=e; f+=g; f^=g>>4; a+=f; g+=h; \
g^=h<<8; b+=g; h+=a; h^=a>>9; c+=h; a+=b; \
}
void hash_init( struct ctx * c ) {
c->a=c->b=c->c=c->d=
c->e=c->f=c->g=c->h= 0x9e3779b9; /* the golden ratio */
mix(c->a,c->b,c->c,c->d,c->e,c->f,c->g,c->h);
}
void hash_compress( struct ctx * c, int32 x[8] ) {
c->a += *x++, c->b ^= *x++, c->c += *x++, c->d ^= *x++;
c->e += *x++, c->f ^= *x++, c->g += *x++, c->h ^= *x++;
mix(c->a,c->b,c->c,c->d,c->e,c->f,c->g,c->h);
}
void hash_extract( struct ctx *c, int32 h[4] ) {
*h++ = c->a + c->e, *h++ = c->b + c->f;
*h++ = c->c + c->g, *h++ = c->d + c->h;
memset( c, 0, sizeof(*c) );
}
Byte order and padding are the same as with SHA1, except that the state
is 8 words instead of 5.
I know that this function is not cryptographically secure... it's pretty
easy to generate collisions if you have complete control of two blocks
of data, since the mix function can easily be run backwards. But.. can
someone learn something about the data if they have just the hash? I
think if the data is no longer than than 32 bytes, and if the opponent
knows the data length, then it's possible, but what if it is longer
than, say, 512 bits?
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Authenticating a PIN Without Compromising the PIN
Date: Tue, 10 Oct 2000 05:39:13 GMT
Paul Rubin wrote:
>
> "Mat" <[EMAIL PROTECTED]> writes:
> > Why can't you have the server generate a random number and give it
> > to the client. The client would then hash its pin with the number
> > and return the result to the server. The server would do the same
> > and compare the results to see if they match. The pin would never
> > be sent over the network.
>
> Unless there's a shared secret key between the client and server
> that's incorporated into the hash, your protocol is vulnerable to a
> brute force against the PIN by an attacker who knows the hash
> function.
How about this: Use the PIN as an encryption key, and send back to the
server the [encrypted] random value. Is this different from the above?
I'm not certain... I think it is, but I might be mistaken.
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Rijndael test vectors
Date: Tue, 10 Oct 2000 05:39:29 GMT
Roger Schlafly wrote:
>
> Brian Gladman wrote:
> > Welcome to the endian world of AES!
> > A world I hope we can remove by getting the specification right on
> > such matters.
>
> Yes. I once implemented DES based on the spec, and then discovered
> that others used the bits in a different order. It seems the
> official spec talked about bits, but not bytes, leaving the
> order of bits in a byte ambiguous.
That's because DES was originally intended to ONLY be used in hardware.
Who cares about bytes, when what you're putting together is gates?
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Possible secure CRC using shrinking?
Date: Tue, 10 Oct 2000 05:40:10 GMT
I don't know how good this idea is, so I'd like some comments...
First, take you data, and compute the CRC of it. Then, using the same
polynomial as the CRC used, use the CRC as the seed of a self-shrinking
LFSR. For an N bit CRC, discard 2N bits from the SSLFSR, then output
the next N bits. Is this a secure hash?
Also, is it (in general) a valid one-way function to use an N+1 bit
SSLFSR, load your N bits of input into the state, turn on the top bit,
then discard 2N bits, and finally output N bits?
Note that I would, of course, be using a primitive irreducible as the
CRC polynomial, in all cases.
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: No Comment from Bruce Schneier?
Date: Tue, 10 Oct 2000 05:40:14 GMT
Forrest Johnson wrote:
>
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> says...
> >
> > I guess that is why I never became
> >a manager. Its hard for me to lie.
> >
> >David A. Scott
> >
> Try again, Mr. Scott. Have you forgotten the claims you made a year
> or so ago about altering software in fielded weapons systems? I
> challenged you to prove those claims and you were unable to do so.
> Not only are you a liar, you are an accomplished one.
An accomplished liar? Don't you mean an unskilled liar? I mean, if he
were a good liar, he'd be able to give^W make up some sort of proof for
his fallacious claims, and it would be presented in such a way so as to
be difficult for us to say "that's wrong."
Fortunately, DS's understanding of english grammar is so poor that he
won't be able to parse that sentence, and improve his lying ability.
Thus, his silly yapping will be easy to recognize as just that.
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Looking for paper
Date: Tue, 10 Oct 2000 05:39:39 GMT
I recall seeing a paper where data was compressed using a static huffman
tree (with 0 and 1 labels on the branches randomly swapped), and the
tree hidden... and analysis was done to attempt to recover the tree. I
don't, however, recall *where* I saw the paper... I think it was a .ps,
or .ps.gz, not a .pdf or .html document.
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: David Eppstein <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Mon, 09 Oct 2000 22:44:51 -0700
In article <[EMAIL PROTECTED]>, Mike Oliver
<[EMAIL PROTECTED]> wrote:
> At the risk of playing clueless straight man here, let me point
> out that if validating a proof is P, then finding a proof is
> ipso facto NP, since you can guess the proof and then check
> if your guess is correct in P time.
There's an important technicality you're forgetting: the size of the proof
might not be polynomial in the size of the original problem.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
[EMAIL PROTECTED] http://www.ics.uci.edu/~eppstein/
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Authenticating a PIN Without Compromising the PIN
Date: Mon, 09 Oct 2000 22:46:49 -0700
Benjamin Goldberg wrote:
> How about this: Use the PIN as an encryption key, and send back to the
> server the [encrypted] random value. Is this different from the above?
> I'm not certain... I think it is, but I might be mistaken.
This is trivial to break. Just try encrypting the random value with
every possible PIN. The one that matches is the winner.
DS
------------------------------
From: "DeSilva" <[EMAIL PROTECTED]>
Subject: working with huge numbers
Date: Tue, 10 Oct 2000 07:39:27 +0200
I would like to implement some encryption into software, but have come
across the obvious problem of doing math on huge numbers. How to device two
500 digit numbers with eachother..
Can anyone in here please explain to me how this is normally done?
Are the numbers converted into a new numeric system which is based on ex 256
in stead og 10 so each digit fits into a byte, or... how??
------------------------------
From: Mike Oliver <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Mon, 09 Oct 2000 22:55:01 -0700
David Eppstein wrote:
>
> In article <[EMAIL PROTECTED]>, Mike Oliver
> <[EMAIL PROTECTED]> wrote:
>
>> At the risk of playing clueless straight man here, let me point
>> out that if validating a proof is P, then finding a proof is
>> ipso facto NP, since you can guess the proof and then check
>> if your guess is correct in P time.
>
> There's an important technicality you're forgetting: the size of the proof
> might not be polynomial in the size of the original problem.
Yep, missed that.
------------------------------
From: Nico Benschop <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Tue, 10 Oct 2000 05:51:40 GMT
Mike Oliver wrote:
>
> Ross Smith wrote:
> >
> > Mark William Hopkins wrote:
> >> Pshaw. Reviewing a proof is not difficult. That's P-time.
> >> FINDING the proof, on the other hand, that's NP-time or worse.
> >> Since P is not equal to NP, then reviewing is easier than finding.
> >>
> >> Therefore, it should be fairly easy to spot the flaw in the paper.
> >> No demo programs are needed.
> >
> > Ah, but that "...or worse" gives them an out. If reviewing a proof
> > is P-time, but *finding* the proof is *worse* than NP-time,
> > then reviewing can still be easier than finding without
> > contradicting P=NP.
>
> At the risk of playing clueless straight man here, let me point
> out that if validating a proof is P, then finding a proof is
> ipso facto NP, since you can guess the proof and then check
> if your guess is correct in P time.
^^^^^^^^^^^^^
I don't know about "ipso facto", but should'nt that be P instead of NP ?
I understand you're putting the P-test in a guessing loop, which latter
is assumed also P (but could'nt the large guessing space cause that
'random search' to be NP ?-) Re: Ape types Shakespeare play... -- NB.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: AES Runner ups
Date: Tue, 10 Oct 2000 05:54:20 GMT
On Tue, 10 Oct 2000 04:52:24 GMT, Greggy <[EMAIL PROTECTED]>
wrote, in part:
>So if Rijndael is the winner, are there any runner ups that would take
>its place if a significant weakness were discovered soon?
Well, of the 15 algorithms submitted, five were finalists, and all
five were believed to be secure - Rijndael was picked because it was
smaller and faster. So, yes, there are four runner-ups that can also
be considered.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Possible secure CRC using shrinking?
Date: Mon, 9 Oct 2000 22:43:59 -0700
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I don't know how good this idea is, so I'd like some comments...
>
> First, take you data, and compute the CRC of it. Then, using the same
> polynomial as the CRC used, use the CRC as the seed of a self-shrinking
> LFSR. For an N bit CRC, discard 2N bits from the SSLFSR, then output
> the next N bits. Is this a secure hash?
If I understand you right, you compute a CRC on the data, and then output a
function of that CRC. If that's the case, it's not a secure hash -- it's
trivial to find collisions on the original CRC.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 10 Oct 2000 06:26:05 GMT
In <[EMAIL PROTECTED]> Nico Benschop <[EMAIL PROTECTED]> writes:
]Mike Oliver wrote:
]> > Ah, but that "...or worse" gives them an out. If reviewing a proof
]> > is P-time, but *finding* the proof is *worse* than NP-time,
]> > then reviewing can still be easier than finding without
]> > contradicting P=NP.
]>
]> At the risk of playing clueless straight man here, let me point
]> out that if validating a proof is P, then finding a proof is
]> ipso facto NP, since you can guess the proof and then check
]> if your guess is correct in P time.
] ^^^^^^^^^^^^^
]I don't know about "ipso facto", but should'nt that be P instead of NP ?
No. He means that if checking whether the proof is correct is P then by
definition, finding the proof is NP. It cannot be "worse" than NP.
------------------------------
From: "Lyalc" <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Tue, 10 Oct 2000 17:33:40 +1000
Greggy wrote in message <8ru73v$abb$[EMAIL PROTECTED]>...
[snip]
>As a US citizen, I have even a greater problem with CAs. I don't need
>them, but they need me and despite that they are pawning such a
>ridiculous system off - which makes me wonder just how dangerous they
>are to the internet.
very
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encryption processing with intermediate permutations
Date: Tue, 10 Oct 2000 08:57:31 +0200
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
> > Bryan Olson wrote:
> > > Mok-Kong Shen wrote:
>
> > > > So does that imply that there is a factor of the order of
> > > > 1000 in comparison with cracking the original block cipher?
> > > > If not, why?
> > >
> > > Of course not. It does not imply, or even suggest, that there
> > > is a tractable attack on the original block cipher.
> >
> > Let me see whether the following makes it more clear for
> > you:
> >
> > Permutations are discrete entities. Nevertheless, one can
> > say that there are permutations that are close to one
> > other, i.e. neighbours. What if I use permutations that
> > are not the identity but close to it? Does it mean that
> > the job then becomes 'suddently' extremely easy as you
> > claimed?
>
> Please do not fabricate claims or quotes and attribute them to
> me.
Is the following a genuine quote from a previous post of
yours or not???
> > Olson:
> > | You specified a pseudo-random permutation. I wrote that a
> > | block with the properties that support the attack probably
> > | exists among about a thousand blocks. If the identity is
> > | one of the inter-round permutations, such a block will not
> > | exist.
If the answer is 'no' please kindly say that and clearly.
If the answer is 'yes', then my response was the following
in my last post (which you however snipped):
In practice it is not easy to obtain good PRNG and hence
good random permutations. To get bad ones, including the
identity, is rather simple. According to your previous
post, I could make one of the inter-round permutations to
be the identity and be immune to your attack. That's no
problem for me, if necessary. There being n rounds (cycles),
I can afford to have one inter-round permutation being
the special one, the identity.
So through this trivial modification (simply leaving out
one inter-round permutation, while maintaining the other
inter-round permutations as before) my scheme becomes
immune to your attack according to what is quoted from
you above exactly. Do you have anything to say to that
now??
M. K. Shen
===================================
Was sich ueberhaupt sagen laesst, | Whatever can be said
laesst sich klar sagen; | can be clearly said;
und wovon man nicht reden kann, | and silence must be kept
darueber muss man schweigen. | on what one cannot tell.
|
Ludwig Wittgenstein | (a translation)
(1889 - 1951)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: working with huge numbers
Date: Tue, 10 Oct 2000 09:05:21 +0200
DeSilva wrote:
>
> I would like to implement some encryption into software, but have come
> across the obvious problem of doing math on huge numbers. How to device two
> 500 digit numbers with eachother..
Read e.g. the book by Knuth, The Art of Computer Programming,
vol. 2. Your question has been often asked. You could dig
out that in the archive (if you can). There are well-debugged
packages. You don't have to re-invent the wheel.
M. K. Shen
> Can anyone in here please explain to me how this is normally done?
> Are the numbers converted into a new numeric system which is based on ex 256
> in stead og 10 so each digit fits into a byte, or... how??
------------------------------
** 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
******************************
