Cryptography-Digest Digest #713, Volume #13 Mon, 19 Feb 01 02:13:00 EST
Contents:
Re: "Shuffled ARC4" revisited ("r.e.s.")
Re: "RSA vs. One-time-pad" or "the perfect enryption" (Steve Meyer)
Re: Super strong crypto (Boris Kazak)
Re: Key expansion. ("Todd Lewis")
Re: "RSA vs. One-time-pad" or "the perfect enryption" ("Douglas A. Gwyn")
Re: Key expansion. ("Douglas A. Gwyn")
Re: National Security Nightmare? (John Savard)
Re: Key expansion. ("Michael Brown")
Re: My encryption system..... ("Michael Brown")
Re: "RSA vs. One-time-pad" or "the perfect enryption" ("John A. Malley")
Re: "Shuffled ARC4" revisited (Guy Macon)
Re: speed vs security (Guy Macon)
----------------------------------------------------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: "Shuffled ARC4" revisited
Date: Sun, 18 Feb 2001 18:06:03 -0800
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote ...
| "r.e.s." wrote:
| > "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote ...
| > | "r.e.s." wrote:
| > | > For any stream cipher, it seems to be a potential weakness
| > | > that each encrypted byte can be matched to the corresponding
| > | > byte of known plaintext.
| > | That's not a general property of stream ciphers.
| > It is in the present context of byte-stream ciphers.
| > If we generalize to stream ciphers using other than
| > byte-size symbols, then the same property exists in
| > those terms. Have I missed something constructive
| > in your comment?
|
| Yes, namely that stream ciphers can be "autokey" or convolutional.
| In which case there is little to distinguish them from block
| ciphers on this score.
I see what you mean. From the Handbook of Applied Crypto., it
appears that the class of ciphers I have in mind are those called
"synchronous" stream ciphers. ("Synchronization" seems to be the
"matching" property that I was trying to describe.)
--r.e.s.
------------------------------
From: [EMAIL PROTECTED] (Steve Meyer)
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Reply-To: [EMAIL PROTECTED]
Date: 19 Feb 2001 02:40:15 GMT
I am not sure but there may be another class. Namely, cryptography in
which the encryption and decryption methods are kept secret.
Say have a method the combines various public key and
symmetric key algorithms (i.e. lot of different kinds of steps).
Since there is the possibility that a one way pad algorithm or other newly
discovered algorithm is hidden in the method, it may be unbreakable.
Of course, new security problem of "really" keeping method secret is
introduced. It may even be true that exhuastive search would not work.
Say, plain text is encoding of human gene that is not one of the genes
recently discovered by the Human Genome Project. There is no way to
know if correct plain text is determined.
I think Cryptographers would say that subject of Cryptography is
algorithms which are publicly and formally specified. Idea is that
this allows confidence from exhaustive and public study of algorithm. But
advantage of shifting problem to include secret algorithms is that
it avoids any hidden conventions in current formalist mathematics.
I gave a rump session talk at recent Asia Crypt on related topic
of why tere was a 5-8 year time period between discovery of public key idea
and workable RSA method. One reason is that back then many more people
were betting on "P==NP". I am uploading to IACR contributed papers
data base this week (or maybe next) my slides and refernces from
talk.
Also, this possible fourth algorithm class is usually studied as "information
hiding". Just my two cents.
/Steve
On Fri, 16 Feb 2001 00:03:43 GMT, John Savard
<[EMAIL PROTECTED]> wrote:
>On Thu, 15 Feb 2001 15:59:13 +0100, "Sebastian Gottschalk"
><[EMAIL PROTECTED]> wrote, in part:
>
>>Both RSA and DSS are not the answer, because the inverse factorization is a
>>trapdoor, still time consuming, but how long will it be??? Is there any real
>>unbreakable algorithm where both keys are not the same?
>
>No.
>
>There is no algorithm with the unbreakability of the one-time-pad that
>functions like a public-key cryptosystem.
>
>Essentially, one can divide ciphers up into three classes.
>
>1)
>The one-time-pad and its equivalents.
>
>It is completely unbreakable, but for a given amount of key, you can
>only send an equivalent amount of messages. So you have to exchange
>keys in advance - and you must allow for the possibility of having to
>make another exchange of keys when you run out.
>
>2)
>Conventional ciphers.
>
>Here, you have a short, convenient key. But theoretically, it can
>always be broken: once you've sent a message longer than the key, it
>can at least be broken by a brute-force attack. But you can make the
>key long enough to make that impractical, and you can make the cipher
>as complicated as you want.
>
>So you don't have provable unbreakability, but you can get so
>elaborate that there really isn't much to worry about.
>
>3)
>Public-key ciphers.
>
>Here, you have to create information that you give to people which
>tells them how to send messages to you. You keep secret, though,
>something additional which lets you read those messages.
>
>Since what you sent let people write the messages, how to read them is
>- must be - implicit in what you sent.
>
>The only reason this works as a cipher system is because there happens
>to be a mathematical 'trick' it is based on.
>
>There doesn't seem to be a way around it. If you want convenience, you
>have to pay for it with a loss of security.
>
>John Savard
>http://home.ecn.ab.ca/~jsavard/crypto.htm
--
Steve Meyer Phone: (415) 296-7017
Pragmatic C Software Corp. Fax: (415) 296-0946
220 Montgomery St., Suite 925 email: [EMAIL PROTECTED]
San Francisco, CA 94104
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Super strong crypto
Date: Mon, 19 Feb 2001 03:47:52 GMT
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > I guess that the purpose is to defeat those attacks that
> > are based on the availability of some (fairly large)
> > amounts of materials encrypted with the same key.
>
> Yes, it's an attempt to address the problem (certainly
> in theory, and often in practice) of using a few initial
> bits of entropy as the sole protection for many megabytes
> of data (whose source characteristics are known). The
> conventional public "solution" to this is either block
> chaining, which adds no entropy, or periodically
> negotiating another key, which is awkward or infeasible
> in many environments. I would like a solution along the
> lines of my straw-man proposal, if it can be shown to be
> sufficiently secure.
==============================
Without going into much detail, here is the system that I use
sometimes for one-to-one communication with my son in Moscow.
We have the same file in our systems which we duplicated
using a trusted channel (sending a floppy with the friend),
This file, essentially random, serves as the source of keys,
it is permanently kept on floppies, not on hard drives.
Now when I encrypt a message, I select from this file a
sequence of bytes, say starting from offset 27493, highlight
27 bytes and use these as the key for the cipher. The
encrypted message is attached to the regular E-Mail, the
content of which is: "use 27493,27". For any observer of the
traffic, this gives no information about the key, for us
this allows never to use the same key twice.
Unfortunately, this system does not adapt very well to the
multi-party communications.
Best wishes BNK
------------------------------
From: "Todd Lewis" <[EMAIL PROTECTED]>
Subject: Re: Key expansion.
Date: Mon, 19 Feb 2001 04:20:32 GMT
First of all, I'd like to introduce myself to the group. I have had an
interest in cryptography for quite a while, but recently my interest has
been greatly piqued. It will be some time before I understand all of the
math, though!
With regards to this question, isn't this scheme vulnerable to a MITM
attack? My understanding of one-way hashes is that the authentication is
done in one of two ways:
1. The authenticator ("Bob" for this example, and sorry if it's insulting to
use such a cliche) either has a copy of Alice's password, and can perform
the same one-way hash and compare his result with the value that Alice sent,
or;
2. Bob has a copy of the hashed password. This option means that Bob will
know if Alice sent the right hashed value, but doesn't know Alice's actual
password.
However, it seems that if Eve has a copy of Alice's hashed password, she can
pose as Alice whenever she wants. Thus, using this hash to encode a session
key would still be vulnerable, even if Eve doesn't know the value of Alice's
un-hashed password.
Is my understanding correct here, or am I missing something?
Very respectfully,
Todd
"Cristiano" <[EMAIL PROTECTED]> wrote in message
news:96obi3$86m$[EMAIL PROTECTED]...
> I have a password constituted from few characters and I want to expand it
> (to at least 128 bits) for use it like session (secret) key for an
algorithm
> to symmetrical key (e.g. rijndael).
> How could I do?
>
> Cristiano
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Mon, 19 Feb 2001 05:03:43 GMT
Steve Meyer wrote:
> I am not sure but there may be another class. Namely, cryptography
> in which the encryption and decryption methods are kept secret.
We don't worry much about those, because often enough in practice
there will be ways of finding out which system was used. Thus
Kerckhoff's dictum: the secrecy of an encryption system must not
depend on lack of knowledge of the general system, but resides in
the lack of knowledge of the specific key. (We could add that it
should also not depend on lack of knowledge about the plaintext
characteristics.) By the way, the general process of figuring out
what system was used via analysis of message properties is called
"cryptodiagnosis".
> Say have a method the combines various public key and symmetric
> key algorithms (i.e. lot of different kinds of steps).
Sooner or later something like this seems to occur to everyone in
this field. The problem is that either a single fixed complex
system is used, in which case cf. Kerckhoff, or else part of the
key is used to select the structure of the system, which is just
the standard general system + key situation with less regularity
than in many traditional systems. The real question is whether
much security is gained by the irregularity. One thing we are
sure of is that the system needs to be carefully designed so that
the key-derived structure doesn't have weaknesses due to "resonance".
> Since there is the possibility that a one way pad algorithm or
> other newly discovered algorithm is hidden in the method, it may
> be unbreakable.
One-time pad is ruled out, because if that were a possible
component you'd have to set up an OTP key distribution system,
in which case why not always use just the OTP instead of
assembling components into something not known to be as strong?
> ... It may even be true that exhuastive search would not work.
> Say, plain text is encoding of human gene that is not one of the
> genes recently discovered by the Human Genome Project. There is
> no way to know if correct plain text is determined.
What you mean is a PT source with very low entropy. Such a
source makes the cryptanalysis difficult for nearly any system,
not just the kind you describe.
Note that genetic protein sequences have nonnegligible entropy.
Indeed, HMMs have been used to characterize (model) them.
> advantage of shifting problem to include secret algorithms is that
> it avoids any hidden conventions in current formalist mathematics.
Why do you think cryptosystem weaknesses are due to "conventions
in formalist mathematics"? If anything, deficiencies in
*cryptanalytic capabilities* might be due to limitations
in one's handling of mathematics.
> I gave a rump session talk at recent Asia Crypt on related topic
> of why tere was a 5-8 year time period between discovery of public
> key idea and workable RSA method. One reason is that back then
> many more people were betting on "P==NP".
It will be interesting to see your argument. I know of no
evidence that this was a factor. If you turn the question
around and ask, why did workers for government cryptologic
organizations get there first, an obvious answer would be:
They had more experience, more support, and more at stake.
Note that I've been arguing that P?=NP is not very important
in practical cryptology.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Key expansion.
Date: Mon, 19 Feb 2001 05:11:08 GMT
Todd Lewis wrote:
> First of all, I'd like to introduce myself to the group.
Welcome!
> With regards to this question, isn't this scheme vulnerable to a MITM
> attack? ...
I don't think that Cristiano wanted to do anything more than encrypt
messages securely (without having to keep a copy of the key bits).
The password would have to be known to both legitimate parties.
The MITM, not knowing the password, has no recourse other than
cryptanalysis; any wrong attempt to meddle would be readily
detectable by the receiver, because the decrypted message would
make no sense.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: National Security Nightmare?
Date: Mon, 19 Feb 2001 05:35:30 GMT
On Sat, 17 Feb 2001 23:08:39 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote, in part:
>As to "optimism", a few hops back in this thread I said
>what was needed was to attend to the education and
>upbringing of people so as to (more nearly) attain a
>condition where technically knowledgable folks would
>rarely agree to work for evildoers regardless of the
>material rewards that might be offered. I didn't
>imply that we had already attained that condition.
But while that would seem to be a desirable condition to attain, even
a necessary one, as deadlier technologies loom in our future, say,
nanotechnology, for example...attaining it seems difficult. As I've
noted, ordinary consumer products today harness mightier forces than
they did in past times.
How can you expect a supermarket checkout clerk to spot a terrorist?
When we have different countries in the world, with different values
and histories, an otherwise normal and sane person from a country long
embittered by strife could be an agent of terrorists.
Making people in general more responsible in their behavior is a fine
idea. But setting up a priesthood to rule over techology is not.
Thus, how to move far enough to be useful in the direction you have
outlined is unclear.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: Key expansion.
Date: Mon, 19 Feb 2001 19:22:03 +1300
"Cristiano" <[EMAIL PROTECTED]> wrote in message
news:96obi3$86m$[EMAIL PROTECTED]...
> I have a password constituted from few characters and I want to expand it
> (to at least 128 bits) for use it like session (secret) key for an
algorithm
> to symmetrical key (e.g. rijndael).
> How could I do?
>
> Cristiano
You'll still only have "a few characters" of entropy, so brute force sounds
like a big problem here :)
Cheers,
Michael
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: My encryption system.....
Date: Mon, 19 Feb 2001 19:26:25 +1300
Summary: Read the FAQ :)
Michael
"Richard Heathfield" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Keill_Randor wrote:
> >
> > It seems that you are all ignoring my challenge.. Oh well...
>
> Challenges are generally a sign that you don't understand who reads
> sci.crypt. Read the FAQ.
>
> >
> > The encryption system I have, (in a response to other posts on this
board),
> > IS different and a generation ahead of any other encryption system in
the world
>
> That's easy to claim and hard to prove. Read the FAQ.
>
> > that I know of. Also, (in response to other posts), a one-pad cipher
IS NOT
> > the best system possible. Mine is.
>
> Again, easy to claim and hard to prove. It is already known that OTP is
> not perfect (although I believe it is agreed that, if the key is unknown
> and the plaintext is unknown, then the very best the enemy can do is
> randomly corrupt the message). Key distribution and bitflipping attacks
> for known plaintext are both problems.
>
> That one-time pads are not as perfect in the real world as they are in
> theory does not imply that your system is better than a one-time pad.
> Read the FAQ.
>
> > To understand why that is the case, you
> > have to understand exactly what data encryption is about in the first
place.
>
> I think there are plenty of people here who have a fair idea of what
> data encryption is about. Read the FAQ.
>
> > This seems to be the number one problem with everyone at the minute:
> > No-one understands the problem, so no wonder nobody, (apart from
myself),
> > has actually solved it.
>
> So you have solved a problem that only you understand, and in which
> nobody else is the slightest bit interested? Read the FAQ.
>
> > All data encryption is about is changing a peice of information into
another, in
> > such a way as to allow you a) to get it back later, and b) stop any
> > 'unauthorised' people finding out what it originally was.
>
> This earth-shattering conclusion is already known to most people in
> sci.crypt. Read the FAQ.
>
> > The ULTIMATE
> > solution, therefore, is to split a peice of information into two or more
> > EXISTING (innocuous) peices of information that CANNOT INDIVIDUALLY BE
PROVEN
> > TO BE ENCRYPTED..................
>
> What cryptanalysis have you done on this? How does it stand up to
> known-plaintext attacks, for example? What is your splitting algorithm?
> Read the FAQ.
>
> > My system at it's best can do this, (Though I have no doubt that it will
be
> > very difficult).
>
> Is it even worth writing? Find out, by explaining exactly what you
> intend. Read the FAQ.
>
> > The by-product of this, is being able to turn ANY peice of information
into ANY
> > peice of information, which again, makes it uncrackable. (And
completely screws
> > up a lot of laws I know about).
>
> "Uncrackable" is easy to claim and hard to prove. Read the FAQ.
>
> >
> > At it's best, (if splitting it into two or more existing peices isn't
possible),
> > my system can do a:
> >
> > Compound, non-repeating, multiple solution, multiple key, multiple
algorithm,
> > mutiple dimension, multiple depth, variable size encrypt, with multiple
phase
> > and multiple direction encoding, and (optional) Multiple variable
ciphers....
> >
> > Trust me, if I encrypted something with all of this attached, then
NO-ONE would
> > ever crack OR solve it, without knowing EVERYTHING about it.
>
> Whenever you say "Trust me", I say "Snake oil". Read the FAQ.
>
>
> > Still looking for a job..... (Any offers???). (I cannot drive though,
and I am
> > currently broke...).
>
> Making yourself look clueless in sci.crypt isn't the best way to get a
> job. Read the FAQ.
>
>
> > (P.S. If no-one else has what I have, does that make me King
Cryppie???).
>
> No. Read the FAQ.
>
>
>
> --
> 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, C books, etc: http://users.powernet.co.uk/eton
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Sun, 18 Feb 2001 22:23:07 -0800
"Douglas A. Gwyn" wrote:
>
[snip]
>
> What you mean is a PT source with very low entropy. Such a
> source makes the cryptanalysis difficult for nearly any system,
> not just the kind you describe.
>
> Note that genetic protein sequences have nonnegligible entropy.
> Indeed, HMMs have been used to characterize (model) them.
There's been a number of references to Hidden Markov Models and
cryptanalysis in various threads over the past few months. I just
found (yesterday) a good (IMO) introduction to statistical language
learning, hidden markov models and probabilistic grammars - "Statistical
Language Learning" by Eugene Charniak, MIT Press, 1993 - ISBN
0-262-53141-0 - at a Borders bookstore.
Are there other books on the subject you'd recommend - especially any
covering cryptanalysis with hidden markov models?
Thanks for any pointers,
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: "Shuffled ARC4" revisited
Date: 19 Feb 2001 06:59:42 GMT
Scott Fluhrer wrote:
>
>Since the weakness is hypothetical, it appears rather difficult to evaluate
>if this random change makes the cipher stronger against that specific
>weakness, and especially difficult to evaluate if it strengthens the cipher
>enough to make up for the additional execution time the revised cipher would
>take.
>
>Why do I harp on execution time? Because it is trivial to come up with
>changes that appear to make the cipher more secure at the cost of time.
>Then, the question becomes, given that you have decided to make this cipher
>more secure, then is this change a reasonably efficient way to do it?
>
Being concerned with efficiency is fine, but you shouldn't assume
that everyone cares about it. Many cipher users have cycles,
memory and disk space to burn, and the only effect of an inefficient
cipher is to slow down the screen saver by 0.1%.
I am much more concerned with the arguments that complicating the
process in any way increases the chance of human error, and that
modifying a well-studied algorithm opens up the possibility of a
new and unknown weakness.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: speed vs security
Date: 19 Feb 2001 07:08:24 GMT
- wrote:
>I'm writingan app, and for x reason, the text needs to be stored in
>encrypted form. W're talking 200K of text maximum, but there's a good 15
>second wait if I try to encrypt/decrypt that much text.
The answer could be as simple as displaying the first screenfull
at once and doing the decryption while the user thinks about what
to do next. A well written Palm App should be able to come up
at once and do lenghty operations in the background.
I am more concerned with your basic philosophy. Palm Apps stay in
memory all of the time. You seem to have designed something that
wiil encrypt and stop working under some circumstances - what is
the trigger? I suspect that the users will power down the palm
with the data unencrypted most of the time.
------------------------------
** 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
******************************
