Cryptography-Digest Digest #476, Volume #13 Tue, 16 Jan 01 05:13:00 EST
Contents:
Re: A Small Challnge (test test)
Re: multiple anagramming? (Terry Ritter)
Re: Is this triple-DES variant secure? (Kenneth Almquist)
Re: NSA and Linux Security (William Hugh Murray)
Re: A security proof for ECDSA (Roger Schlafly)
Re: Comparison of ECDLP vs. DLP (William Hugh Murray)
Re: future trends in asymmetric cryptography (Dido Sevilla)
Re: A Special Deck of Encryption Cards (Dido Sevilla)
Re: NSA and Linux Security (Greggy)
Re: Any ideas on breaking this? (Richard Heathfield)
Re: Is this triple-DES variant secure? ("Jakob Jonsson")
Re: Any good source of cryptanalysis source code (C/C++)? ([EMAIL PROTECTED])
Re: Any good source of cryptanalysis source code (C/C++)? (David Schwartz)
Re: multiple anagramming? (Mok-Kong Shen)
----------------------------------------------------------------------------
From: test test <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: A Small Challnge
Date: Mon, 15 Jan 2001 23:34:22 -0500
Benjamin Goldberg wrote:
> 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).
I think we are picking nits again. With public key encryption we could
recover the public key from the cipher text provided we knew the encryption
algorithm and knew the channel the cipher text was being passed. My
"formal" nature would like to strictly classify this as something like RSA
where the strength of the system does not rely on keeping anything secret
except the secret key. Perhaps we would not be too restrictive if we drew
parallels to a formal public key system. In the case where the security of
the PKS is protected by the disparity in the difference of time it takes to
multiply two large primes together VS factor the larger composite we can
calculate the effort. Any system that uses a similar "disparity in the
difference" factor could be defined as a public key system I suppose. I
am not sure the mathematical representation can be proven unless the system
is better defined, but that is probably just my own weakness.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: multiple anagramming?
Date: Tue, 16 Jan 2001 05:21:14 GMT
On Mon, 15 Jan 2001 20:46:04 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt Benjamin Goldberg
<[EMAIL PROTECTED]> wrote:
>[...]
>Ritter could add a
>"Multiple Anagraming" entry in his glossary (and also an entry for
>"Transposition Cipher," which is a very odd thing to omit!)
http://www.io.com/~ritter/GLOSSARY.HTM#CipherTaxonomy
http://www.io.com/~ritter/GLOSSARY.HTM#Transposition
http://www.io.com/~ritter/LEARNING.HTM#ClassicalCryptanalysis
Do I need to do more?
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Kenneth Almquist)
Subject: Re: Is this triple-DES variant secure?
Date: 16 Jan 2001 05:18:49 GMT
[EMAIL PROTECTED] (David Wagner) wrote:
> It seems that your attack can be improved.
>
> Encrypt M M M M M M M M where M is any single block.
Or more generally, encrypt A B A B A B A B, where A and B are arbitrary
block values.
> Then we'll have
> F2[k] = F2[k+4] for all k,
> whence
> F2[1] + F2[2] + ... + F2[8] = 0.
Jonsson's number's scheme made F2[1] be an IV value, so there is an off
by one error here. This should be F2[2] + F2[3] + ... + F2[9] = 0.
> Note that
> D(C[1], K1) + D(C[3], K1) + D(C[5], K1) + D(C[7], K1)
D(C[2], K2) + D(C[4], K2) + D(C[6], K2) + D(C[8], K2)
> = F2[1] + F2[2] + ... + F2[8]
= F2[2] + F2[3] + ... + F2[9]
> = 0.
> Thus we can guess K1 [actually K2] and verify its correctness using
> the above equation.
>
> This attack requires 2^58 trial decryptions and a single chosen plaintext,
> which seems to improve on your attack (which needs 2^56 chosen texts, if I
> understood correctly).
>
> Moreover, this attack requires no information whatsoever on the IV's,
> so it works even when, e.g., the IV's are sent encrypted.
>
> Did I make any mistakes?
Your attack looks correct to me (except for the numbering issues which
I noted above). The requirements (one chosen plaintext or chosen
ciphertext, and 2^58 operations) are simple enough that this qualifies
as a practical attack as opposed to a theoretical attack, so I think
we can declare this idea dead and cart its corpse off to the graveyard
of failed cryptographic ideas.
Kenneth Almquist
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: NSA and Linux Security
Date: Tue, 16 Jan 2001 05:33:50 GMT
digiboy | marcus wrote:
>
> You must remember, Hitler (and his government) was voted into power in
> Germany by a massive majority of the voters.
Indeed, I must remember the truth and that is not it. I assume, Sir,
that you speak out of ignorance rather than out of any intent to
deceive. However, that is a very dangerous untruth, not to say a lie.
In 1930 the Nazis won only 18% of the vote entitling them to only 107
seats in the Reichstag. Even in a multi-party system they were still
only the second largest party. They deliberately destabilized both the
economy and the government. In the presidential election held on March
13, 1932, Hitler ran against von Hindenburg for President and got 30% of
the vote to Hindenburg's 49%. In the runoff Hitler got 36% but
Hindenburg got 53% without campaigning. In the Riechstag elections of
July of 1932, the Nazis got 37% of the vote. Not a majority.
It was not until January of 1933 after months of blood in the streets,
the failure of the von Papen and Schleicher governments, and the promise
of Hitler to consent to Papen as vice chancellor and only four Nazis in
government that president Hindenburg named Hitler Chancellor. By that
time the Nazis were the largest party in the Riechstag but they were
still far from a majority. They became a majority only when Hitler had
begun to rule by decree. They became a majority only after the Nazis
had burned the Reichstag. They became a majority when they outlawed
other parties. They became a majority when they had turned the state
police on the populace. Are you ready?
Your words suggest that you might be surprised. Readers of the history
of the Greek and Roman Republics were not surprised. The founders of
the United States, who had studied that history, would not have been
surprised. Students of language know that tyrant and demagogue date
from the Greek republics and originally had a different meaning from
those that they have today.
On the night that Hitler became Chancellor General Erich Ludendorf wrote
to von Hindenburg, "By appointing Hitler Chancellor of the Reich you
have handed over our sacred German Fatherland to one of the greatest
demagogues of all time. I prophesy to you this evil man will plunge our
Reich into the abyss and will inflict immeasurable woe on our nation.
Future generations will curse you in your grave for this action."
Elected by a majority, Indeed.
> Think about that for a second or two, and how it affects the angle you're coming
>from.
I have, Sir. I have thought long and hard about it and the implications
for both our countries. I think about the implications for a country
with a parliamentary system in the absence of a strong two party system.
I think about the implications for a constitutional republic without the
electoral college. I am not encouraged in either case.
William Hugh Murray
>
> --
> [ marcus ] [ http://www.cybergoth.cjb.net ]
> [ ---- http://www.ninjakitten.net/digiboy ]
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: A security proof for ECDSA
Date: Mon, 15 Jan 2001 21:44:17 -0800
Alfred John Menezes wrote:
> You can find a (preliminary) version of a paper by Dan Brown at
> www.cacr.math.uwaterloo.ca under "Technical reports". It is
> paper #34 under "2000 Technical reports".
> The paper proves that ECDSA is existentially unforgeable by
> adaptive chosen-message attacks assuming that the group employed
> is a generic group, and that the hash function employed is
> collision resistant. Of interest is that the proof technique does
> not seem to apply to the DSA.
> As with all security proofs, the importance of this proof should
> always be discussed in the context of the security model and
> the assumptions made.
I'll have a look. At first glance, the paper appears to use a
random group model that is analogous to the random oracle model.
Instead of assuming that your hash function is a random one
pulled from a big family of hash functions, you assume that the
group is pulled randomly from a big family of groups.
In the end, tho, it doesn't use any math properties of elliptic
curves or anything like that. After some abstract nonsense, it
just assumes that the EC group is an appropriate instantiation,
whatever that means.
The proof requires that the group be parameterized in an efficient
way that is easy for ECDSA than for DSA. I doubt that this makes
ECDSA more efficient that DSA, but I haven't read the paper.
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Comparison of ECDLP vs. DLP
Date: Tue, 16 Jan 2001 05:58:35 GMT
David Wagner wrote:
>
> 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.
Agreed. In common law there are (practically) none. Under the
penalties of perjury, one may always repudiate a signature or an act.
One may always assert forgery. (One may even do so in Utah unless one
makes the error of using a digital signature.) Of course the only
effect is to transfer the burden of proof to the other party. In real
property transactions this burden is usually easily met by the
signatures and testimonies of the witnesses and notaries. In chattel
transactions it is not usually material.
We have been led, not to say trapped, by the Europeans into talking
about "non-repudiation" when for most purposes accountability is good
enough.
William Hugh Murray
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: future trends in asymmetric cryptography
Date: Tue, 16 Jan 2001 14:13:38 +0800
Jan Fedak wrote:
>
> Hi guys.
>
> Do you have any good ideas? I should write a conclusion for my thesis
> till tomorrow and after some hard hours at work I feel empty...
>
> Thanks for any promotions.
>
The first thing you guys need to do is stop the USPTO from granting
algorithm patents. Arguably the main reason why asymmetric crypto has
been effectively limited to RSA and ElGamal all these years is because
of these software patents. We would have probably seen much more
research in the field of asymmetric crypto had these patents never been
granted. I'm sure a lot of early researchers in the same field were
discouraged from further study by the threat of patent litigation from
RSA or whoever. Now that the RSA patent is gone, more research might
result, but that won't prevent some starry-eyed researcher thinking of
becoming the next data security giant after Ronald Rivest from filing
yet another patent and starting the process all over again. Be thankful
IBM didn't file patents on SP-networks and Feistel structures back in
the seventies when DES was first produced!
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: A Special Deck of Encryption Cards
Date: Tue, 16 Jan 2001 14:27:49 +0800
John Savard wrote:
>
> Actually, one could even consider the Hebrew alphabet, but the
> applicability is limited...
>
As a matter of fact, the 22 trump cards of a Tarot deck, or the Major
Arcana as they are sometimes called, have precise Hebrew letter
equivalents in esoteric studies, especially relating to Cabalistic
stuff. I get the distinct feeling that a cipher scheme similar to what
John is proposing may in fact have been used by Medieval occultists to
hide information from the Inquisition or the uninitiated...
The Fool - Aleph
The Magician - Beth
The High Priestess - Gimel
The Empress - Daleth
The Emperor - Heh
The Hierophant - Vav
The Lovers - Zayin
The Chariot - Kheth
Strength - Teth
The Hermit - Yod
The Wheel of Fortune - Kaph
Justice - Lamed
The Hanged Man - Mem
Death - Nun
Temperance - Samekh
The Tower - Peh
The Star - Tzaddi
The Moon - Qoph
The Sun - Resh
Judgement - Shin
The World - Tau
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Tue, 16 Jan 2001 06:52:00 GMT
Shawn Willden <[EMAIL PROTECTED]> wrote:
> 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?).
Actually, it was because of WWI that the president was given powers to
regulate the trade of the US with potential war time enemies. After
the war, the great depression took place and (if you study history) FDR
and the congress technically, legally declared the citizens of the US
enemies of the US so that we could be regulated just like our enemies
were - by the president. According to a 1973 US Senate report on this
issue, since 1933 (FDR coming to power), we have never lived under
constitutional rule, but emergency rule which allows us to be regulated
under maritime authority by the president (as he had jurisdiction over
the pirates of the high seas) rather than common law courts. There is
MUCH to be said about that time in history. FDR had to have been the
worse president ever to sit in the white house. He did more damage to
this country than any other. Yet, no president has chosen to undo what
he did, not even Eisenhower nor Reagan, so you cannot hold them in
esteem either. They have all sold out. Only JFK stood against those
who had the most to lose going back to constitutional rule and you know
what happened to him.
Oh, actually we don't know all that happened because the Warren
commission used that "national security" to cover up the obvious.
And it can't happen today?
--
I prefer my fourth amendment rights over a dope free
society, even if the latter could actually be achieved.
Sent via Deja.com
http://www.deja.com/
------------------------------
Date: Tue, 16 Jan 2001 08:18:02 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Any ideas on breaking this?
slim to none wrote:
>
> hello,
>
> i realise you must get soooo bored with people asking these questions,
> but... (there's always a but)
>
> could you please have a go at cracking the text below?
Er, no.
> i keep seeing these
> kinds of encryptions at the bottom of otherwise harmless looking spam,
Actually, you have this exactly the wrong way round.
The "encryptions" are just randomly generated text, designed to steer
the spam safely through anti-duplicate filters.
<snip>
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: Re: Is this triple-DES variant secure?
Date: Tue, 16 Jan 2001 10:12:28 +0100
I'm not sure that this works... It seems to me that C[i+4] = C[i] (except
when i=1), so the sum
D(C[2], K2) + D(C[4], K2) + D(C[6], K2) + D(C[8], K2)
will be zero for any choice of K2. Please tell me if I'm missing something.
What we can do is that we can encrypt
M X M Y M X M Y M Y M X M Y,
where M, X, Y are arbitrary, except that X and Y must be different. Put m =
E(M, K1), x = E(X, K2), y = E(Y, K2). Then
F1[2] = F1[1] + m
F1[3] = F1[1] + m + x
F1[4] = F1[1] + x
F1[5] = F1[1] + x + y
F1[6] = F1[1] + m + x + y
F1[7] = F1[1] + m + y
F1[8] = F1[1] + y
F1[9] = F1[1]
F1[10] = F1[1] + m = F1[2]
F1[11] = F1[1] + m + y = F1[7]
F1[12] = F1[1] + y
F1[13] = F1[1] + x + y
F1[14] = F1[1] + m + x + y = F1[6]
F1[15] = F1[1] + m + x = F1[3]
This implies that F2[10] = F2[2], F2[11] = F2[7], F2[14] = F2[6], and F2[15]
= F2[3], which in turn implies that
D(C[2], K2) + D(C[6], K2) + D(C[10], K2) + D(C[14], K2) =
F2[2] + F2[3] + F2[6] + F2[7] + F2[10] + F2[11] + F2[14] + F2[15] = 0.
Moreover, C[2], C[6], C[10], C[14] are all different, so this sum will be
different from 0 with high probability if K2 is not the correct key. This
attack is just a slight modification of David Wagner's attack, so again we
need one chosen plaintext and 2^58 trial decryptions.
Do you agree?
BTW, I forgot to mention that my very first observation was inspired by the
Biryukov-Wagner sliding attacks...
Jakob
"David Wagner" <[EMAIL PROTECTED]> skrev i meddelandet
news:93vra6$cu9$[EMAIL PROTECTED]...
> Jakob Jonsson wrote:
> >F1[k+1] = F1[k] + E(M[k], Ki)
> >F2[k+1] = E(F1[k+1], Kj)
> >C[k] = E(F2[k] + F2[k+1], Ki)
> >
> >(+ = xor). For odd k, i=1 and j=2, and for even k, i=2 and j=1.
>
> It seems that your attack can be improved.
>
> Encrypt M M M M M M M M where M is any single block.
> Then we'll have
> F2[k] = F2[k+4] for all k,
> whence
> F2[1] + F2[2] + ... + F2[8] = 0.
> Note that
> D(C[1], K1) + D(C[3], K1) + D(C[5], K1) + D(C[7], K1)
> = F2[1] + F2[2] + ... + F2[8]
> = 0.
> Thus we can guess K1 and verify its correctness using the above equation.
>
> This attack requires 2^58 trial decryptions and a single chosen plaintext,
> which seems to improve on your attack (which needs 2^56 chosen texts, if I
> understood correctly).
>
> Moreover, this attack requires no information whatsoever on the IV's,
> so it works even when, e.g., the IV's are sent encrypted.
>
> Did I make any mistakes?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Any good source of cryptanalysis source code (C/C++)?
Date: Tue, 16 Jan 2001 09:17:27 GMT
Tom,
When will you learn not to reply to posts if you aren't willing to help.
This kind of answer is wasting people's time. So you either help or keep
quiet because how annoyed you are is your business only and isn't of any
interest to anyone else.
Regards,
Brice.
In article <9408jr$i47$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> 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/
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Any good source of cryptanalysis source code (C/C++)?
Date: Tue, 16 Jan 2001 01:39:07 -0800
[EMAIL PROTECTED] wrote:
> When will you learn not to reply to posts if you aren't willing to help.
> This kind of answer is wasting people's time. So you either help or keep
> quiet because how annoyed you are is your business only and isn't of any
> interest to anyone else.
Actually, the question is a waste of time and bandwidth. If the
response helps to minimize future wastes of time and bandwidth, then it
doesn't waste anything.
DS
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: multiple anagramming?
Date: Tue, 16 Jan 2001 11:07:48 +0100
Benjamin Goldberg wrote:
>
> The problem with suggesting the library is that my local library doesn't
> have any crypto books. It takes about the same time to request a book
> with interlibrary loan as it would take to order it for purchase from a
> bookstore.
I am sorry to express some opinions concerning your original
post that would certainly displease you. If all books are
freely available on the internet (or in whatever form), don't
you think that the motivations of (at least plenty of) authors
to write books and that of (all) publishers to publish them
would disappear? Why do there exist copy rights? Most libraries
attempt to cope with the needs of those who couldn't/wouldn't
buy books for financial reasons. But because their bugets are
limited, they can only satisfy the desire of a subset of
the target population and even that only partially. To help
them, one should consider donating to the local libraries
one's own books that one no longer needs for instant access
at home and that are not present there for use by other people.
M. K. Shen
========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
** 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
******************************
