Cryptography-Digest Digest #923, Volume #12 Sat, 14 Oct 00 06:13:00 EDT
Contents:
Re: On block encryption processing with intermediate permutations (Bryan Olson)
Re: Why trust root CAs ? (David Schwartz)
Re: SDMI - Answers to Major Questions (Stephan T. Lavavej)
Re: Why trust root CAs ? (Greggy)
Re: Why trust root CAs ? ([EMAIL PROTECTED])
Re: A new paper claiming P=NP (MS)
Re: Why trust root CAs ? ([EMAIL PROTECTED])
Re: SDMI - Answers to Major Questions (Scott Craver)
An important message concerning A. Plotnikov's paper (Stas Busygin)
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: On block encryption processing with intermediate permutations
Date: Sat, 14 Oct 2000 08:27:56 GMT
Mok-Kong Shen:
> David Hopwood has a second post and I have just responded
> to that. Maybe I'll able to discuss with him further
> quite near to the line of your attack in the next time.
Sure, though I don't see a whole lot left to discuss.
I (like half the nation it seems) caught a severe cold or
mild flu and took a few sick days this week. That left me
with some lying-in-bed-and-thinking-about-stuff time, so
let's look at attacking the modified scheme.
I'll include the two major modifications: First, we
dis-allows modes of use in which the attacker could get
multiple texts from the same PRNG state. Second, we'll take
out one of the between-round permutations. Since which
permutation to omit was unspecified, I'll assume the
middle-most one.
As before, I'll make the assumption of a 16-round (8
round-pair) cipher, in which a block is two words.
The PRNG is unnamed, and hence un-attackable. The cipher is
specified only as a Feistel cipher. I'll take the attack to
the point of isolating the last rounds-pair, so we can solve
for the last two round keys without regard to the complexity
or key material of earlier rounds.
The scheme is described so as to work on messages of any
positive integral number of blocks, and again I'll use
chosen plaintext of chosen sizes. The chosen plaintexts are
very different from the previous attack.
First I'll encrypt the same single-block message a few
hundred times. Call the plaintext (u, v), where u and v are
the two words of the block.
On two words, there are two possible permutations. The
permutation operation is done 6 times, so there are 64
possible outcomes. The permutation is pseudo-random, so
they're all equally likely. It should take about 300 tries
to get all 64 possible outcomes.
Each ciphertext in the set of 64, has a sibling in the set
that was induced by the same five permutations followed by
the opposite permutation. If we can match blocks with their
siblings (how is considered below), then we have enough
information to attack the last two rounds of the Feistel
cipher, independently of the first 14 rounds.
Specifically, if we have a ciphertext block of two words (a,
b) and its sibling is (c, d), then there exist words x and y
such that,
a = x ^ f(k15, y),
b = y ^ f(k16, a),
c = y ^ f(k15, x),
d = x ^ f(k16, c).
Where k15 and k16 are the last two round-keys and f is the
non-linear function of the Feistel cipher. This gives us
four equations with four unknowns. It may still fail to
have a unique solution because of the nature of the f
function, but with more sibling pairs the equations dominate
the unknowns, since all will have the same k15 and k16.
How to solve the equations depends on the Feistel cipher,
but most will not survive with only two of their rounds thus
exposed. Obtaining the last two rounds keys is devastating
for most Feistel ciphers, and once we have them we can work
on k13 and k14 using the same method if necessary.
Now how do we determine which pairs of 1-block ciphertext
descended from the same state before the last permutation?
If the Feistel cipher allows for very efficient solution of
the equations, we might just do it by exhaustive guessing.
If not, then we use more chosen ciphertext. Again we use
the same message many times, but this time the message is
two blocks (four words) long. The two blocks are the same
as each other, and the same as our one-block plaintext for
which we got the 64 possible outcomes. If the one-block
message we used was (u, v) then the two-block message is
(u, v, u, v).
Now we have four words, so there are 24 possible
permutations, But there are not 24^6 different, equally
likely outcomes. Suppose the two blocks going into a
permutation are the same; say the words are (x, y, x, y).
Eight of the 24 permutations keep the two blocks the same;
four of them producing (x, y, x, y), and four producing
(v, u, v, u). If the two blocks are the same going in to
a round-pair (or a round-quadruple in one case), then
they are the same coming out.
If the plaintext is two equal blocks (u, v, u, v), then we
have a (1/3)^6 = 1/729 chance of the ciphertext being two
equal blocks, say (a, b, a, b). (The chance of this
happening without hitting six equality-preserving
permutations is negligible.) If it does happen, then (a, b)
will always be one of the 64 ciphertext we obtained from the
one-block plaintext (u, v).
Also a 1/729 chance is hitting five permutations that
preserve block equality and then one that sets the two
blocks with their halves reverse, as in (x, y, y, x). In
this case, we get a ciphertext of the form (a, b, c, d),
where (a, b) and (c, d) both in our set of 64 one-block
outcomes. Then the blocks (a, b) and (c, d) are the
siblings that we need to set up the equations that solve for
the last round-pair.
In one message, each of the 32 sibling-pairs has a 1/729 *
1/32 = 1/23328 chance of appearing as such in the output.
There may also be false-hits; there can be outputs
(a, b, e, f) where (a, b) and (e, f) are both among the 64
single-block outputs, but the two blocks are not sibling
pairs. But the most likely false pairings have half the
sibling pair probability.
The false-hits happen when a permutation other than the last
one takes (x, y, x, y) to (x, y, y, x) or (y, x, x, y) and
subsequent permutations keep the each word-pair together.
The chance of a permutation keeping each word-pair together
is 1/3, the same as the chance of preserving block equality.
But the 1/3 chance is spread over four possible outcomes, so
a specific false-hit has a lower probability than a specific
sibling-pair.
[Again we regard as negligible the chance of hitting such an
output without hitting a permutation that necessarily
induces it.]
How we choose to put together the sibling-pairs depends on
how expensive it is to solve the equations for the last two
rounds. We might just encrypt our two-block until we hit
the 1/729 chance and try to solve using it. To be
reasonably sure we have correct sibling pairs, we could
encrypt half a million times, so each of the sibling-pairs
should appear enough times to distinguish it from the lower
probability false-pairs.
There is exactly one other class of ciphertexts from our
two-block plaintext with members as probable as the
equal-blocks and the sibling pairs. They appear when the
first five permutations preserve block equality, and the
last takes (x, y, x, y) to (x, x, y, y) or (y, y, x, x). We
can recognize these outputs by their frequency, and they
give us an alternative set of equations with which to attack
the last two rounds. Given that the output is (a, b, c, d),
there are words x and y such that,
a = x ^ f(k15, x), c = y ^ f(k15, y),
b = x ^ f(k16, a), d = y ^ f(k16, y).
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 01:49:20 -0700
[EMAIL PROTECTED] wrote:
> This model can be further generalised.
>
> Let's suppose you generate your own public key and register it with
> your bank at time of opening your account. Then whenever you sign a
> transaction with your private key, your bank knows it is you.
>
> But this could also apply to any other situation where a signature (or
> any other verification of identity) is currently required - simply
> register your public key and then use your private key to authenticate
> your identity in all transactions with that party from then on.
I think you'll find that if you do this, you recreate the PKI. First,
you'll want a central repository of whose key is whose. Second, you'll
want one place to go to revoke a key should it be compromised. And so
on.
DS
------------------------------
From: stl/*This_is_a_comment*[EMAIL PROTECTED] (Stephan T. Lavavej)
Subject: Re: SDMI - Answers to Major Questions
Date: Sat, 14 Oct 2000 08:50:54 GMT
>Stupid SDMI people. I routinely listen to MP3 shoutcast streams at 128
>kbps, and it sounds very good. If your watermark makes it worse then
>phhtt!
MP3 compression is NOT transparent at 128kbps. In fact, it's quite
bad. Anyone who doesn't hate 128kbps doesn't care about quality.
Even 256 or 320 kbps doesn't quite cut it; the codec always mangles
specific input signals, even those found in regular music. I listen
to MP3, but when I burn CDs, I go straight from my original WAVs. I
do indeed agree that SDMI is stupid, stupid, stupid.
-*---*-------
Stephan T. Lavavej
http://quote.cjb.net
stl/*This_is_a_comment*[EMAIL PROTECTED]
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 08:54:03 GMT
In article <[EMAIL PROTECTED]>,
Paul Rubin <[EMAIL PROTECTED]> wrote:
> Greggy <[EMAIL PROTECTED]> writes:
> > But you missed the real problem with CAs. Can Verisign answer the
> > following for you:
> >
> > Can you prove none of your employees took a bribe and provided me
with
> > a bad cert?
>
> How is it *possible* to do that in a way that you couldn't detect
instantly?
Okay, bad question. Let me rephrase. Can you prove none of your
employees took a bribe and provided a thief with a signed certificate
with his public key instead of mine allowing him to act as a man in the
middle?
But the bribe issue was the key to the question. Same as the other
questions, the question was worded badly but the key issue is the same.
> > Can you prove that your certification process is adequate for my
needs?
> The certification practices statement is public. The only person who
> can decide if it's adequate is you.
Fair enough.
> Look, Verisign is pretty straight about what guarantees they give you.
> If you have financial losses from problems with a Verisign cert,
> they'll cover you up to some amount (the amount depends on the type of
> certificate). What do you want them to do instead? What would *you*
> do instead?
See bottom...
>
> Suppose you run a grocery store and a customer wants to write you a
> check and shows you a valid-looking drivers license as ID. Can you
> know the DL isn't forged? Of course not; but you generally take it
> anyway. You've decided that the probability of a forged drivers
> license times the amount of loss caused by a bad check for some
> groceries is less than the profit you'd forgo by declining the check.
> Making that kind of probability-based decision is called risk
> management. With enough transactions you'll get bitten a few times,
> but less often than if you didn't ask for ID at all.
>
> Certificates in a PKI are a risk management device, not an absolute
> guarantee of anything. Verisign's marketing pitch is that
> authenticating with a class 2 Verisign PKI certificate is about as
> good as looking at someone's drivers' license: they can be faked, but
> not easily. A class 3 certificate is supposed to be as good as
> looking at a passport: harder to forge than a drivers license, but
> still not impossible. I don't claim to believe those estimates, but
> in any case, the certs have a certain level of security that's not
> trivial and not infinite. This is good enough for most of the
> business purposes that they're sold for.
>
I have already said that the best way to limit risk here is to get the
certificate straight from the financial institution. I have offered
two ways. One is to read it from a published source, like the WSJ.
Another is get it from the bank itself (say walk into a branch office)
and install it as a self signed or non signed (if possible)
certificate. You don't need it signed - you don't need to trust anyone
else to sign off on the certificate. You know where it came from - the
bank itself. That is the best. It is not as easy as a CA certificate
that is auto/transparent downloadable, but you asked and there is my
answer. It is simply better because you need not trust anyone but the
bank. And if you cannot trust the bank themselves, why would you do
business with them?
Your answer deals with risk management. My answer deals with
eliminating unnecessary risks.
--
If I were a cop, I would refuse to go on any no knock raid.
But then, I am not a cop for basically the same reasons.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 10:29:03 GMT
On Sat, 14 Oct 2000 19:43:28 +1000, "Lyalc" <[EMAIL PROTECTED]>
wrote:
>If you replace Public Key with Password, this models works just as well, and
>works today, at zero incremental cost.
Scheme outlined has advantages over passwords which may justify the
incremental costs. EG:
- a password is inherently less secure since it relies on keeping the
password secret, and yet password is known to all entities/devices for
which you use that password. A public key can be put on a bill board
without lessening security.
- using a public key approach allows enables encryption of data unique
to the user, increasing security.
- the use of a device to handle the registration and authentication
simplifies the process from the point of view of the end user and
obviates the need to handle, remember and keep secure multiple
passwords.
PB
>Lyal
>
>
>[EMAIL PROTECTED] wrote in message
><[EMAIL PROTECTED]>...
>>On Sun, 08 Oct 2000 05:10:53 +0100, David Hopwood
>><[EMAIL PROTECTED]> wrote:
>[snip]
>
>>This model can be further generalised.
>>
>>Let's suppose you generate your own public key and register it with
>>your bank at time of opening your account. Then whenever you sign a
>>transaction with your private key, your bank knows it is you.
>>
>>But this could also apply to any other situation where a signature (or
>>any other verification of identity) is currently required - simply
>>register your public key and then use your private key to authenticate
>>your identity in all transactions with that party from then on.
>>
>>This could extend to verifying your identity to hardware. Your car,
>>your house locks, all these could be built to enable you to initially
>>register a public key and only open/operate from that point on when a
>>random session id is returned signed by the private key corresponding
>>to your public key.
>>
>>It could also apply to software - replacing the need for all the
>>myriad passwords one accumulates for different systems, as you could
>>associate your public key with your various computer userids on each
>>system and then return a signed random session ID to verify yourself
>>at logon.
>>
>>Furthermore, for those concerned with privacy and the fact that the
>>public key is a unique id across all applications, enabling traffic
>>analysis of your movements, habits and usage, one could simply allow
>>that any person can have as many public keys as they want. This could
>>present problems for the user in remembering which key they'd
>>registered with which entity/device, but then we manage to handle a
>>number of different house keys, car keys passwords etc etc.
>>
>>But lets suppose that:
>>. the method of carrying and issuing the public key and storing and
>>using the private key is a PIN protected or bio-recognition smart card
>>. they cost $9 apiece at your local newsagent;
>>. come in a security sealed package from reputable suppliers;
>>. there is common software/hardware to enable you to generate or
>>load your own key;
>>. they have a roughened front surface on which you can write Car,
>>House, Third National Bank, HomePC, WorkID etc etc, and
>>. a hole drilled in the top right to enable them to be kept on a key
>>ring...
>>
>>I have neglected issues of card loss, key revocation etc etc, but I
>>dont think these are insurmountable.
>>
>>As I understand it the major barrier to this approach is that there is
>>no universal, simple, secure, portable thingy that can carry the keys,
>>and do the processing required. The obvious candidate is a smart
>>card, but I understand they simply do not (yet) have the processing
>>power to handle digital signing using an assymetric key (eg RSA).
>>Offloading the processing presumably creates security problems.
>>
>>PB
>>
>>
>>>- --
>>>David Hopwood <[EMAIL PROTECTED]>
>>>
>>>Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
>>>RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
>>>Nothing in this message is intended to be legally binding. If I revoke a
>>>public key but refuse to specify why, it is because the private key has
>been
>>>seized under the Regulation of Investigatory Powers Act; see
>www.fipr.org/rip
>>>
>>>
>>>-----BEGIN PGP SIGNATURE-----
>>>Version: 2.6.3i
>>>Charset: noconv
>>>
>>>iQEVAwUBOd+BhzkCAxeYt5gVAQEqEAf/RCjAXabrazj+oceIj+d8/WC/I+91mHwc
>>>P5URHoux22bLAN8XOWBe0TK04UVwtR1d0Pt/mA1S1svTbrJ+JAFH3hR1hrr/88eU
>>>Z1MwH+lbK96oYZbN6sSI3gmvyg/zPS4zXkgW6L9WJfP4Na6wrcjvAH1E9kpGlWcD
>>>UtzO+ida9CsKo63FW9KZ+nCBvztt1iqZSZI7v/XSfXL35VuzvJq30JPKeyiSA7Lr
>>>2TqH6v4mma6Scph641KnLWH1BNBavyq2jTvbix5aWkiFnTFvrsAQvpAeGPlsYB0W
>>>+fOuDdEbmOIowjR/oMR0A+kZ7lDDhhgkwYvQ4mLvEKsCXr2Obq2DEw==
>>>=+OuX
>>>-----END PGP SIGNATURE-----
>>>
>>
>
>
------------------------------
From: MS <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Sat, 14 Oct 2000 11:37:57 +0200
Eric Lehman wrote:
>
> On page 10 he shows how to direct the edges of a graph G to get a DAG,
> which defines a poset. Fine. Take a minimum chain decomposition.
> Fine. Now we get definitions:
>
> A path P in G is said to be "stretched" on the set of chains that it
> intersects. Is this correct?
>
> The definition of "densely stretched" confuses me. A path P in G is
> said to be "densely stretched" on the set of chains it intersects
> *provided* no two adjacent vertices on the path lie in the same chain.
> Is this correct? Or is it that no two vertices connected by an edge in
> G can lie in the same chain? As I understand it, every simple path is
> "stretched" on some set of chains, but not every simple path is "densely
> stretched" on some set of chains. Correct?
Well, I am now on page 10, too, and perhaps I can help. One has to be careful,
of course, to distinguish between "path of a poset" (=chain) and "undirected
path", these are different things. An undirected path U in G is said to be
densely stretched on the set of chains it intersects provided no two
*non*-adjacent (=independent) vertices of U lie in the same chain.
> Then I get down to this: "It is easy to see that a simple undirected
> path of the length L can be densely stretched on not less than
> ceil(L/2)+1 paths of P..."
That's correct: if the chains in P are allowed only to contain adjacent vertices
of an undirected path U, then each chain cannot contain more than 2 vertices of
U. Thats because if you arbitrarily take 3 or more vertices from U, at least 2
of them are not adjacent.
> Where are the quantifiers in this
> assertion? Is he making a statement that holds FOR EVERY poset that can
> be generated from a graph G by his procedure, EVERY minimum chain
> decomposition, and EVERY path of length L in G?
Yep. But there seems to be no magic in it.
> ...
>
> To clarify matters, can you explain his assertion with regard to the
> following example?
>...
IMHO your path *is* densely streched on the chains, *because* each chain
contains only adjacent vertices.
Hope this helps
- Michael -
--
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Why trust root CAs ?
Date: Sat, 14 Oct 2000 10:39:01 GMT
On Sat, 14 Oct 2000 01:49:20 -0700, David Schwartz
<[EMAIL PROTECTED]> wrote:
>
>[EMAIL PROTECTED] wrote:
>
>> This model can be further generalised.
>>
>> Let's suppose you generate your own public key and register it with
>> your bank at time of opening your account. Then whenever you sign a
>> transaction with your private key, your bank knows it is you.
>>
>> But this could also apply to any other situation where a signature (or
>> any other verification of identity) is currently required - simply
>> register your public key and then use your private key to authenticate
>> your identity in all transactions with that party from then on.
>
> I think you'll find that if you do this, you recreate the PKI. First,
>you'll want a central repository of whose key is whose. Second, you'll
>want one place to go to revoke a key should it be compromised. And so
>on.
If the key is associated with your chosen id at each bank or whatever,
then there is no need for a central repository.
Key revocation, I grant you, is more problematic.
PB
------------------------------
From: [EMAIL PROTECTED] (Scott Craver)
Subject: Re: SDMI - Answers to Major Questions
Date: 14 Oct 2000 09:39:00 GMT
Stephan T. Lavavej <stl/*This_is_a_comment*[EMAIL PROTECTED]> wrote:
>
>MP3 compression is NOT transparent at 128kbps. In fact, it's quite
>bad. Anyone who doesn't hate 128kbps doesn't care about quality.
But this doesn't matter. SDMI is clearly designing a system
to stop common-case piracy, and common-case quality standards
are pretty friggin' low.
-S
------------------------------
From: Stas Busygin <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: An important message concerning A. Plotnikov's paper
Date: Sat, 14 Oct 2000 13:16:02 +0300
Dear All!
The paper has been patched by the author in the following points:
- the definition of the set D(G) (p. 7);
- the description of the initial matching construction (pp. 5-6);
- the definition of the analyzing digraph (p. 30).
According to the publishing rules of Stas Busygin's Repository for
Hard Problems Solving, any stuff in it may be renewed by authors at
any time. So, the pathed file of the paper has been uploaded to
http://www.geocities.com/st_busygin/clipat.html
Please download it. Thanks to all participating in the discussion!
Best regards,
Stas Busygin
email: [EMAIL PROTECTED]
WWW: http://www.busygin.dp.ua
------------------------------
** 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
******************************
