Cryptography-Digest Digest #475, Volume #13 Mon, 15 Jan 01 23:13:00 EST
Contents:
Re: A Small Challnge ("rosi")
Any good source of cryptanalysis source code (C/C++)? ("Haider Ali")
Re: Comparison of ECDLP vs. DLP (Roger Schlafly)
Re: A Special Deck of Encryption Cards (Matthew Skala)
Any good source of cryptanalysis source code (C/C++)? ("Haider Ali")
Re: Any good source of cryptanalysis source code (C/C++)? (Tom St Denis)
Re: NSA and Linux Security (Shawn Willden)
Re: Is this triple-DES variant secure? (Kenneth Almquist)
Re: Comparison of ECDLP vs. DLP (David Wagner)
Re: NSA and Linux Security (Shawn Willden)
Re: A Small Challnge (Benjamin Goldberg)
----------------------------------------------------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: A Small Challnge
Date: Mon, 15 Jan 2001 20:41:08 -0500
Dear Mok-kong,
First, thanks for your interest and questions. (The gratitude also
extends
to Steve and Mike and anybody who has an interest in the QP notion).
I am afraid, I messed up again. But it is so hard to misunderstand,
because
there is the formal part as well.
The best I think is to quote what I said.
>>>> Start Quote
A more formal treatment of QP will follow, but I think the notion
in an informal form may have a wider range of audiences to allow
potentially a larger variety of schemes.
A QP key is an asymmetric cryptographic key with the
^^^^^^^^^^^^^^^^
following special feature: from the viewpoint of the holder
of the secret decryption key, the QP encryption key (which
is made public) ...
^^^^^^^^^^^
So, a re-visit to the notion of 'asymmetry': in the public-
key scheme, there is a knowledge difference between the holder
of the secret decryption key and the general public on the
secret decryption key (i.e. the holder knows everything about
the decryption key but the general public do not), while in QP,
there is in addition a knowledge difference about the publicly
^^^^^^^^
known encryption key as well.
^^^^^
Denote E as an encryption key and D[1], D[2], ..., D[n] as a
set of corresponding decryption keys satisfying:
For any message m, i != j only if
D[i](E(m)) != D[j](E(m)) for sufficiently
many of all the values m, the (plaintext)
message, can take on.
For convenience, 'sufficiently many of' can be 'close to a half
of'.
Denote D as a decryption key and E[1], E[2], ..., E[n] as a
set of corresponding encryption keys satisfying:
D(E[i](m)) = D(E[j](m)) = m
for any 1<=i,j<=n and any m, where E[i](m)=E[j](m) iff i=j.
>>>> End Quote
I just re-emphasize here.
A QP encryption key is an asymmetric key. You may have noticed the
way I referred to the type of scheme. I used 'asymmetric' and 'public' as
well. You should also notice the marked difference in the descriptions of
('definitions of') them. I do not care if one uses different keys for
encryption and decryption, that alone does not qualify as asymmetric
scheme. It is the knowledge difference that counts. Therefore, even if
one keeps the encryption key secret, that does not disqualify the scheme
as an asymmetric one. If it is one, then it is regardless of how it is used.
However, being asymmetric, it does not care if you make the encryption key
public or not.
As to the formal part, I think I need hardly say anything. It is pretty
formal and formal stuff should not have ambiguity. (Appreciate it if you can
let me know which part appears to be ambiguous).
Therefore, you do NOT give up the benefits of PK, you enhance it. As a
matter of fact, you are still doing PK. The schemes under this notion of QP
may be trivial; it may be esoteric to one or two people, but it could be,
IMHO, plainly different.
I must admit that there is one point in the 'second flavour' that is
not made explicit. But I do not think there is the need. Anyway, this is
a challenge, no matter how small, and this implicit part is slightly
challenging.
Having said this, I encourage you to read carefully the formal part. If
you still have questions, I will be very happy to answer in private (so as
to keep the challenge more interesting). I can give you pretty concrete
examples to show exactly what QP is about. So please do not hesitate to ask
me if you still have questions (either by posting or by writing in private
to [EMAIL PROTECTED]).
Finally, I think I need to say just 'a few' words in response to Mike's
post. (Sorry, Mike, I might not have versed the challenge clear.) Mike's
proposal is interesting. The same (or very similar) idea was mentioned
a couple of times about my semi-public keying scheme, in which a same public
key can be used with additional secret which the decryptor also has to
keep a copy of and be able to associate with any individual encryptor. In
that scheme, if the secret is compromised, there could be a certificational
problem (if no other method is involved in the primitive of mutual identi-
fication and session key establishment), but there should be no security
problem. The scheme only provides individualization through the additional
secret, but does not depend on it for security.
QP is not really specifically designed for PKI. It is purely for
asymmetry and trapdoor one-way.
By the way, semi-public and QP are not necessarily mutually exclusive.
Thanks and best regards, and good luck again!
--- (My Signature)
P.S.
Still looking for a development site for my crypto ideas. Anybody
interested or know somebody who might be interested? Let me know. Thanks!
------------------------------
From: "Haider Ali" <[EMAIL PROTECTED]>
Subject: Any good source of cryptanalysis source code (C/C++)?
Date: Tue, 16 Jan 2001 09:12:51 +0800
Hi.....
I am looking for any good cryptanalytic attacks on block ciphers, programmed
in C/C++ (I need the source code).....
Regards
Haider
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Mon, 15 Jan 2001 17:20:47 -0800
Wei Dai wrote:
> In article <93sqj3$a0b$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] says...
> > Don is pointing out the difference between proof-of-possession (POP) of
> > a private key, and proof that a private key logically exists (public-key
> > validation). These concepts are difficult to formalize (I'm not sure
> > if anyone has ever done this), but the intuition can be obtained by
> > considering the following example with traditional discrete log based
> > schemes.
> I think Don was pointing to the ease of public-key validation as an
> advantage of elliptic curve cryptography compared to RSA. But in the
> case of RSA, public-key validation doesn't seem useful or necessary. So
> it's not clear why it might count as an advantage for either side. Do
> you have an example of where the lack of public-key validation for RSA
> would cause a security problem?
Don is worried about about someone constructing a weak RSA key pair,
either deliberately or by accident. Maybe it was generated by a
broken RNG or buggy software. The user then signs messages and
later disavows them. A tricky person might use such a stunt to
back out of a signed contract.
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: A Special Deck of Encryption Cards
Date: 15 Jan 2001 17:16:16 -0800
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>can with little trouble translate from english letters to their latin
>equivilants. Translating english letters to hebrew equivilants is
>significantly harder, due to much less knowledge of that alphabet.
For historical reasons, Hebrew letters are something you would naturally
expect to find written on the cards in a 78-card deck; even something as
unusual as a different random permutation of that alphabet on each card
would go completely unnoticed. The same is not true of the Latin alphabet
- a deck of 78 random permutations of that would obviously be a cipher
device.
--
Matthew Skala
[EMAIL PROTECTED] :CVECAT DELENDA EST
http://www.islandnet.com/~mskala/
------------------------------
Reply-To: "Haider Ali" <[EMAIL PROTECTED]>
From: "Haider Ali" <[EMAIL PROTECTED]>
Subject: Any good source of cryptanalysis source code (C/C++)?
Date: Tue, 16 Jan 2001 09:36:16 +0800
*** post for free via your newsreader at post.newsfeeds.com ***
Hi.....
I am looking for any good cryptanalytic attacks on block ciphers, programmed
in C/C++
(I need the source code).....
Regards
Haider
**** Post for FREE via your newsreader at post.newsfeeds.com ****
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
*** Newsfeeds.com - The #1 Usenet Newsgroup Service on The Planet! ***
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
http://www.newsfeeds.com | http://www.newsfeeds.com
|
* Anonymous posting server! | * Totally Uncensored!
* SUPER Servers! | * Over 80,000 Newsgroups!
* BINARIES ONLY Servers! | * 16 seperate Newsgroup Servers!
* SPAM FILTERED Server! | * Instant access!
* ADULT ONLY Server! | * Multiple OC 3's and OC 12's!
* MP3 ONLY Server! | * 99% Article Completion!
* MULTIMEDIA ONLY Server! | * Months of Retention!
* 7 UNCENSORED Newsgroup Servers | * Lightning FAST downloads!
|
http://www.newsfeeds.com | http://www.newsfeeds.com
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
**** Point your newsreader to post.newsfeeds.com ****
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Any good source of cryptanalysis source code (C/C++)?
Date: Tue, 16 Jan 2001 01:37:00 GMT
In article <94077c$blqps$[EMAIL PROTECTED]>,
"Haider Ali" <[EMAIL PROTECTED]> wrote:
> Hi.....
>
> I am looking for any good cryptanalytic attacks on block ciphers, programmed
> in C/C++ (I need the source code).....
Keep looking.
This question is asked like 50 times a day here... For #### sake
cryptanalysis is not some magic wand. Get a grip and read papers!
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Mon, 15 Jan 2001 18:21:50 -0700
digiboy | marcus wrote:
> What _is_ a reasonable search? If you are searching
> communications and flagging only messages that, say, have a high number
> of phrases and keywords (not forgetting structure) relating to terrorist
> activities, has that been a reasonable search?
I would suppose that depends on whether you call the automated scanning
process a "search". If you do, then no, it doesn't seem like a reasonable
search, because you're scanning all messages. This is like stopping all
cars and sniffing for pot smoke. However, if the scan-and-tag process isn't
a search, but only some sort of an automated probable cause test, then,
assuming the matching algorithm is good enough, it is reasonable to search
the matched messages. Continuing the analogy with drug searches I suppose
this would be akin to profiling? ;-)
[For any that might not be familiar with the term, "profiling" is the
practice of looking at vehicles and their drivers and mentally matching
them agains a profile of likely drug runners. Black dudes with beady eyes
in big mercedes, that sort of thing.]
Shawn.
------------------------------
From: [EMAIL PROTECTED] (Kenneth Almquist)
Subject: Re: Is this triple-DES variant secure?
Date: 16 Jan 2001 02:10:15 GMT
[EMAIL PROTECTED] (David Wagner) wrote:
> This is known as inner chaining, and Eli Biham has shown reasons
> to believe that it is likely to be less secure than outer chaining.
> Take a look at the following papers:
> Eli Biham, ``On modes of operation'', FSE'93.
> http://www.cs.technion.ac.il/~biham/Reports/onmodes.ps.gz
>
> Eli Biham, ``Cryptanalysis of multiple modes of operation'', ASIACRYPT'94.
> http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1994/CS/CS0833.ps
Thanks for the references. I read the second. It appears that the
attacks described in that paper are all dependent on data being passed
from one level to another. One of the simplest cases involves encrypting
twice in CBC mode and once in ECB mode. In this case, decryption works
as shown in the following diagram. Note that one path through the
decryption process has the C[1] data passing through a single encryption
step followed by two XOR operations, producing the plaintext P[3]:
C[1] C[2] C[3] C[4]
| | | |
V V V V
--------- --------- --------- ---------
|DES(K3)| |DES(K3)| |DES(K3)| |DES(K3)|
--------- --------- --------- ---------
| | | |
|-------\ |-------\ |-------\ |
| | | | | | |
V | V | V | V
--------- | --------- | --------- | ---------
|DES(K2)| | |DES(K2)| | |DES(K2)| | |DES(K2)|
--------- | --------- | --------- | ---------
| | | | | | |
--->XOR \----->XOR \----->XOR \----->XOR
| | | |
|-------\ |-------\ |-------\ |
| | | | | | |
V | V | V | V
--------- | --------- | --------- | ---------
|DES(K1)| | |DES(K1)| | |DES(K1)| | |DES(K1)|
--------- | --------- | --------- | ---------
| | | | | | |
--->XOR \----->XOR \----->XOR \----->XOR
| | | |
V V V V
P[1] P[2] P[3] P[4]
To take advantage of this data path, we use a chosen ciphertext attack
which varies C[1] while holding C[2] and C[3] constant. This reduces
the problem of finding K3 to the problem of breaking
P[3] = D(C[1], K3) xor A
where A is an unknown constant. This can be attacked using linear
or differential analysis. A more practical attack is to get two
plaintext/ciphertext pairs (P1, C1) and (P2, C2), and use an exhaustive
search to find a K3 such that
C1 xor D(P1, K3) = C2 xor D(P2, K3)
The inner chaining variant that I presented looks like:
C[1] C[2] C[3] C[4]
| | | |
V V V V
--------- --------- --------- ---------
|DES(K1)| |DES(K2)| |DES(K1)| |DES(K2)|
--------- --------- --------- ---------
| | | |
--->XOR /----->XOR /----->XOR /----->XOR
| | | | | | |
|-------/ |-------/ |-------/ |
| | | |
V V V V
--------- --------- --------- ---------
|DES(K2)| |DES(K1)| |DES(K2)| |DES(K1)|
--------- --------- --------- ---------
| | | |
|-------\ |-------\ |-------\ |
| | | | | | |
--->XOR \----->XOR \----->XOR \----->XOR
| | | |
V V V V
--------- --------- --------- ---------
|DES(K1)| |DES(K2)| |DES(K1)| |DES(K2)|
--------- --------- --------- ---------
| | | |
V V V V
P[1] P[2] P[3] P[4]
Unlike the constructs considered by Eli Biham, every data path
through this construct passes through at least three DES operations,
so it seems unlikely that any of Biham's attacks could be adapted to
work against it. However, Jakob Jonsson has posted an attack that
does work, based on the fact that the IV values don't pass through
all three levels.
Kenneth Almquist
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 16 Jan 2001 02:30:13 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Roger Schlafly wrote:
>Don is worried about about someone constructing a weak RSA key pair,
>either deliberately or by accident. Maybe it was generated by a
>broken RNG or buggy software. The user then signs messages and
>later disavows them. A tricky person might use such a stunt to
>back out of a signed contract.
In my view, non-repudiation seems to be such an exacting requirement
that when you need it, it pervades system design in nearly every aspect.
Given this, I'm not sure it makes sense to compare RSA vs. ECC on such
a tiny aspect of non-repudiation, when there are so many other enormous
consequences of non-repudiation. It is very rare to find systems today
that provide non-repudiation.
That's just my view. (And yes, I know that the argument Roger Schafly
was describing isn't necessarily his view.)
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Mon, 15 Jan 2001 19:11:03 -0700
digiboy | marcus wrote:
> I see no difference in the US where they've been in operation to a major
> extent _at least_ since pre-WWII.
Not much pre-WWII. Heck, for most of the period between WWI and WWII the
U.S. didn't even spy on its *enemies* communications, much less its
citizens, that being an "ungentlemanly" thing to do (what is that quote
from The Black Chamber?).
Shawn
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: A Small Challnge
Date: Tue, 16 Jan 2001 03:28:30 GMT
So it would be like generating an RSA key pair, but instead of
publishing the RSA public key for the world to read, you ONLY transmit
it to the people who are going to send you messages, and you perform
this transmission securely.
Thus, *if* the key of the people who are sending you messages becomes
compromised to an attacker, then the security of the system is reduced
to that of RSA.
If it doesn't get compromised... Hmm. Does anyone know of any attacks
on RSA when the public key isn't initally known to the attacker?
--
Technology which is distinguishable from magic is insufficiently
advanced. (Corollary with Clark's Law).
------------------------------
** 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
******************************