Cryptography-Digest Digest #463, Volume #13 Sat, 13 Jan 01 05:13:00 EST
Contents:
Re: Different DES (John Myre)
Re: 16bit collision resistance hash function? (John Myre)
Re: 16bit collision resistance hash function? (Jim Gillogly)
Re: Electronic resources for cryptology? (RoceKiller)
On cryptographic proofs and their (lack) of concreteness ("Joseph Ashwood")
Documentation on encrypting routines (RoceKiller)
that security proof for ECDSA ?? (David A Molnar)
Re: that security proof for ECDSA ?? (Paul Rubin)
A Small Challnge ("rosi")
Security proof (Benjamin Goldberg)
Re: A Small Challnge (Mok-Kong Shen)
Re: On cryptographic proofs and their (lack) of concreteness (Mok-Kong Shen)
Re: Need of very simple algorithms? (Shawn Willden)
Re: Need of very simple algorithms? (Shawn Willden)
----------------------------------------------------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Different DES
Date: Fri, 12 Jan 2001 15:09:20 -0700
I was going to apologize profusely for the wrong URL but
it appears that NIST has just now moved and redesigned
their FIPS site. The DES document is now:
http://csrc.nist.gov/publications/fips/fip46-3/fips46-3.pdf
The FIPS page is:
http://csrc.nist.gov/publications/fips/index.html
Oh, well. I guess I'll go fix my bookmarks now.
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: 16bit collision resistance hash function?
Date: Fri, 12 Jan 2001 15:18:18 -0700
"[Basic]" wrote:
<snip>
> In fact I calculate the hash value over a 64bit long value and my problem is
> that while transmitting the last few bits can get lost. As the 16bit hash
> value is also transmitted the receiver should be able to reconstruct the
> last few (up to ~25) bits by brute forcing and setting up a list of possible
> solutions. This list should be as short as possible.
This is starting to sound like a failure to communicate
the requirements. The question you actually posted has
been answered. If what you really want is to solve a
real problem, the best way to proceed is to describe
the problem. It is possible that a "hash" isn't even
the right tool in the first place.
JM
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: 16bit collision resistance hash function?
Date: Fri, 12 Jan 2001 14:23:02 -0800
"[Basic]" wrote:
> In fact I calculate the hash value over a 64bit long value and my problem is
> that while transmitting the last few bits can get lost. As the 16bit hash
> value is also transmitted the receiver should be able to reconstruct the
> last few (up to ~25) bits by brute forcing and setting up a list of possible
> solutions. This list should be as short as possible.
Then perhaps you should be looking at "error-correcting codes" rather
than hashes.
--
Jim Gillogly
Sterday, 21 Afteryule S.R. 2001, 22:22
12.19.7.15.17, 9 Caban 20 Kankin, Second Lord of Night
------------------------------
From: RoceKiller <[EMAIL PROTECTED]>
Subject: Re: Electronic resources for cryptology?
Date: Fri, 12 Jan 2001 23:30:01 +0100
On Sat, 6 Jan 2001 11:29:45 -0000,
"Mark Hellewell" <[EMAIL PROTECTED]>
used 20 lines to tell us:
>"Richard Cavell" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>>It's difficult to buy specialist books in Australia.
>>The FAQ lists two websites which have both disappeared.
>>Does anyone have any recommended online cryptology resources?
>There are tons of resources, all you have to do is search for them.
Right, but there's a lot of junk too, and it's hard to find the good
stuff, between the bad stuff.
Greetings
RoceKiller
--
{E-Mail: RoceKiller(at)trashcan.dk UIN: #36155647 IRC: #RK at Undernet}
"Facts oph�rer ikke med at eksistere, fordi man ignorerer dem."
Aldous Huxley
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: On cryptographic proofs and their (lack) of concreteness
Date: Fri, 12 Jan 2001 15:18:31 -0800
Recently on sci.crypt there has been a lot of discussion regarding
mathematical proofs, and their validity. These are my thoughts, and
hopefully some answers for some people.
(Almost) Every mathematical proof makes some assumptions. These assumptions
range in assuredness from the mundane (1+1=2), to things that we know are
fundamentally flawed but we use regardless (the random oracle model). Each
of these has varying uses. The main use of these security proofs is in
reducing the specifics that must be examined.
The common assumptions are things like:
The RSA problem is hard
The Discrete Log problem is hard
SHA-1 acts as a random oracle
Given a short list of these assumptions it is possible to make it far easier
to determine if the algorithm in question suits the needs of the situation.
For most purposes, SHA-1 is effectively a Random Oracle, and the RSA problem
is hard. However if the requirements are to have a public key of only 500
bits, and since 512-bit factoring has occured, the RSA problem hardness
assumption is violated.
Proof like this, proofs that define more sharply the requirements for
security, are of great use and interest to those who depend on these
primitives. It not only allows us to judge primitives faster and with better
accuracy, but for maintainance it is at least, perhaps more, helpful. Proofs
about the security of protocols relying on certain basic assumptions become
ever more important. When I finish a protocol I generally hand off the
maintainance of it to someone less capable. Being able to make statements
like, "You need only worry about the Discrete Log problem at 1024 bits and
the strength of SHA-1" greatly reduces the level of expertise needed by that
person.
For cryptanalysis it is also extremely useful. If a proof can be built that
problem X relies only on the strength of it's 2 assumptions (DL-1024 and
SHA-1), then a cryptanalyst can determine that avenues other than attacking
SHA-1 and DL-1024 don't even need to be considered, and real work on the
problem can begin much sooner, with fewer false starts, and a much better
chance for real results.
While the proofs are not of the form, therefore this is provably secure,
they are of great use, and the maintainance and examination of the
primitives and protocols is far less costly. I depend on this kind of proof
every day, some are obvious, some are not, but if my judgement is ever
called into question, I can justify myself.
Joe
------------------------------
From: RoceKiller <[EMAIL PROTECTED]>
Subject: Documentation on encrypting routines
Date: Sat, 13 Jan 2001 00:45:17 +0100
Where do I find documentations on diffrent encrypting routines?
Greetings
RoceKiller
--
{E-Mail: RoceKiller(at)trashcan.dk UIN: #36155647 IRC: #RK at Undernet}
"Facts oph�rer ikke med at eksistere, fordi man ignorerer dem."
Aldous Huxley
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: that security proof for ECDSA ??
Date: 13 Jan 2001 00:03:59 GMT
This looks like it *may* be the security proof referred to by Don Johnson
in a previous thread:
http://eprint.iacr.org/2001/003/
Separating Decision Diffie-Hellman from Diffie-Hellman in
cryptographic groups
Antoine Joux and Kim Nguyen
Abstract. In many cases, the security of a cryptographic scheme based
on Diffie--Hellman does in fact rely on the hardness of the
Diffie--Hellman Decision problem. In this paper, we show that the
hardness of Decision Diffie--Hellman is a much stronger hypothesis
than the hardness of the regular Diffie--Hellman problem. Indeed, we
describe a reasonably looking cryptographic group where Decision
Diffie--Hellman is easy while Diffie--Hellman is equivalent to a --
presumably hard -- Discrete Logarithm Problem. This shows that care
should be taken when dealing with Decision Diffie--Hellman, since its
security cannot be taken for granted.
Category / Keywords. public-key cryptography / number theory, elliptic
curve
Date: received 9 Jan 2001
Contact author: [EMAIL PROTECTED]
I say this because it concerns elliptic curves; I have not yet read it and
don't know how it matches with the remarks about a proof which "applies to
ECDSA but not to DSA."
Thanks,
-David
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: that security proof for ECDSA ??
Date: 12 Jan 2001 18:07:38 -0800
David A Molnar <[EMAIL PROTECTED]> writes:
> This looks like it *may* be the security proof referred to by Don Johnson
> in a previous thread:
Looks completely different from what I can tell.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: A Small Challnge
Date: Sat, 13 Jan 2001 00:31:10 -0500
Here is a little challenge that pertains to "concrete" computational
complexity as well as to cryptography. In specific, it is associated with
a concept called 'Quasi-Public' (QP).
This is a call for the 'demonstration' of the existence of, or the
concrete design of, any cryptographic scheme that may sit with the
_INFORMAL_ notion of QP.
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. Anything that carries the
notion:
"not really public even though made so"
should count. People who are not really engaged in the cryptographic
disciplines, may find the following helpful:
In cryptography, a particular type of schemes are referred
to as 'asymmetric'. 'asymmetric' basically means that the
holder of the decryption key has a level of knowledge about
the cryptographic keys used different from that of those
who do not hold the decryption key. Conventionally, this
asymmetric scheme may also be known as public-key scheme.
Here it means that the encryption key "can" be made public
and that even though an attacker having the publicly
available encryption key and a copy of the ciphered text,
he "cannot" feasibly obtain the original text, "nor" of
course can he feasibly obtain the decryption key from the
public encryption key.
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) is not really made public. In other words,
the understanding and viewpoint of the encryption key is
different between the holder(s) of the secret decryption key
and any other in the general public which includes potential
attackers on the cryptographic scheme.
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.
(With regard to secure schemes, we certainly would not want such
difference to be irrelevant to security)
Any idea, whether practical or not, that even remotely fits the notion
will be welcomed. So here, virtually anything goes! And let us hear from
you!
Now, slightly more formal.
QP in two flavours.
1. For a single encryption key, there can be more than one
corresponding decryption keys that decrypt 'differently' but
unambiguously.
The word "differently" has the following, more precise meaning:
different decipherings gain different pieces of
information about the plaintext (versus getting
different semantics from a same piece of information).
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'.
2. There can be more than one corresponding encryption keys to a
single decryption key, yet the encrypted text (ciphertext), by
any of the multitude of different encryption keys, decrypts (by
this said decryption key) uniquely to the plaintext.
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.
To avoid terrific jokes and extraordinary sense of humour frequently
exhibited in sci.crypt, I go redundant One Time More (Oh, no! Not OTP!):
n=1 should be an exception rather than the norm!
Thank you so very much.
--- (My Signature)
P.S.
Have a friend or know one who likes mental exercises and little
challenges? Pass this on to him and he may enjoy!
One is not limited to any single cryptographic technique. Any tweak
can be applied for a realization of QP.
Of course, nothing should prevent you from combining 1 and 2 in some
sense.
And do not forget the computational complexity part of the story! (Agree
that one has to have a scheme first before talking about its complexity)
Good luck!
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Security proof
Date: Sat, 13 Jan 2001 07:31:27 GMT
I want to try and prove my hypercrypt cipher secure under the assumption
that the byte pair mixing function is a Strong Psuedo-Random
Permutation. To do this, I want to first attempt to show that a reduced
blocksize version is secure, and then show that expanding it does not
weaken its strength.
I informally define a Strong Psuedo Random Permutation as a block cipher
which is secure against an adaptive chosen plaintext and ciphertext
attack.
Notation:
Let M be a SPRP, and M(K) is a particular 2N bit permutation.
Let a, b, c, d each be 1/4 of the 4N bit plaintext.
Let w, x, y, z each be an N bit temp variable
Let e, f, g, h each be 1/4 of the 4N bit ciphertext.
The reduced size cipher is as follows:
(w, x) = M(K0)(a, b)
(y, z) = M(K1)(c, d)
(e, f) = M(K2)(w, y)
(g, h) = M(K3)(x, z)
How do I go about proving that this construct is also an SPRP?
I think it can be done... but I'm not sure how.
I think I should mention that there are some *possible* weak keys, but
I'm going to assume that they won't occur in the actual implementation.
Here's an example:
Suppose that there exists some Ka, Kb, such that M(Ka) = M(Kb)^(-1);
Then, if a=c, b=d, K0=K1=Ka, and K2=K3=Kb, then e=g=a, and f=h=b.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: A Small Challnge
Date: Sat, 13 Jan 2001 09:13:34 +0100
rosi wrote:
>
[snip]
> 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) is not really made public. In other words,
> the understanding and viewpoint of the encryption key is
> different between the holder(s) of the secret decryption key
> and any other in the general public which includes potential
> attackers on the cryptographic scheme.
>
> 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.
Very probably I misunderstood. Do you mean that the
encryption key is not known to the general public but only
to a selected subset of people, including the case of only
one person (a determined single sender)? But then you have
given up the benefit of PK and could use a symmetric
encryption system just as well, don't you?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On cryptographic proofs and their (lack) of concreteness
Date: Sat, 13 Jan 2001 09:46:35 +0100
Joseph Ashwood wrote:
>
[snip]
> While the proofs are not of the form, therefore this is provably secure,
> they are of great use, and the maintainance and examination of the
> primitives and protocols is far less costly. I depend on this kind of proof
> every day, some are obvious, some are not, but if my judgement is ever
> called into question, I can justify myself.
I believe you are evidently right. The only thing one
should always guard against is saying 'This is provably
secure' instead of 'This is provably secure under the
assumptions ......', for some people would unconsciously
ignore the fact that there are generally certain assumptions
underlying a proof and that these assumptions could be
false or considered to be insufficiently secure to be relied
upon in given practical situations.
M. K. Shen
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Sat, 13 Jan 2001 01:58:18 -0700
Paul Rubin wrote:
> Shawn Willden <[EMAIL PROTECTED]> writes:
> > I don't know about that particular microprocessor, but many low-end
> > smart card microprocessors cost well under $1, and they're capable of
> > performing AES operations.
>
> $1 is a lot of money for a low end device. If my company wants to
> ship 100 million smart cards, and AES needs a $1 processor but
> Skipjack needs a 35 cent processor, I'm going to have an awful hard
> time convincing the CEO to give up $65 million from the company's
> bottom line in exchange for some abstract theoretical security
> improvement.
I'm not arguing that you should pay two or three times as much for a
security increase that is irrelevant. I'm really arguing that using weaker
security won't save you any money.
For small volumes, the most important cost factor is going to be whether or
not the device is available off the shelf, so that you're not footing all
of the manufacturing set-up cost. For example, there are currently a large
number of inexpensive chips that implement 3DES in ROM. Most smart card
applications could get along just fine with DES, but the cheap chips are
the high-volume chips and they're 3DES.
For large volumes, the most important cost factor is the number of gates,
which translates into silicon size and density. For 100 million devices
you're going to be better off implementing everything you can in hardware,
rather than in software. A device with AES in silicon will cost less than
a device with a weaker algorithm in software. There won't really be a
substantial difference in cost between an AES hardware implementation and a
hardware implementation of something else, because even with relatively
low-density masks the die size of both will be very small.
And if all that weren't enough, consider that your unit cost will probably
be dominated by other costs anyway. The cost of the chip itself is a
fairly trivial piece of the cost of deploying a smart card. Even with very
high-end, expensive chips, in large volumes the printing, embedding
personalization, packaging and distribution tend to cost more than the
chips do. For comparison, consider that the financial industry figures it
costs between $5 and $8 to deliver a printed, embossed credit card with a
personalized magnetic strip and a hologram to a card holder.
IMO, economies of scale favor the more standard algorithm as long as it's
not excessively expensive, and AES is small, fast and cheap enough to be
used everywhere, even if the security it provides is overkill.
Shawn.
------------------------------
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Sat, 13 Jan 2001 02:02:51 -0700
Mok-Kong Shen wrote:
> I meant those text messages that are sent by handy users.
> (Sorry, if the acronym I used is not universally accepted.)
> A normal handy user doesn't carry any computing device
> with him for running sophisticated encryption algorithms.
> That's the problem.
GSM cellphones carrying smart card chips that are perfectly capable of
implementing AES, even they currently don't. Many of them also have
cryptographic coprocessors that allow them to implement public key crypto.
There is no problem here. Further, the phones themselves have much more
powerful microprocessors which could also easily run sophisticated crypto,
although they don't have any sort of secure key storage.
Shawn.
------------------------------
** 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
******************************
