Cryptography-Digest Digest #726, Volume #13 Wed, 21 Feb 01 00:13:01 EST
Contents:
question1,2,2a,3,4,5,5a,5b,5c,6 ("h4jiwk9j")
Re: New unbreakable code from Rabin? ([EMAIL PROTECTED])
SIX FIGURE SALARIES ("LeeJ")
Re: Indicative key generation, encryption/decryption time ("Joseph Ashwood")
Re: asking for stream cipher resource ("Joseph Ashwood")
Re: question1,2,2a,3,4,5,5a,5b,5c,6 (Paul Rubin)
Re: "RSA vs. One-time-pad" or "the perfect enryption" ("Joseph Ashwood")
Re: Super strong crypto (David Wagner)
Re: Super strong crypto (David Wagner)
Re: [release] OutGuess 0.2 - steganographic tool (Niels Provos)
Re: New unbreakable code from Rabin? ("Malcolm Herring")
Re: New unbreakable code from Rabin? ([EMAIL PROTECTED])
Re: Super strong crypto (Paul Rubin)
----------------------------------------------------------------------------
From: "h4jiwk9j" <[EMAIL PROTECTED]>
Subject: question1,2,2a,3,4,5,5a,5b,5c,6
Date: Tue, 20 Feb 2001 21:09:54 -0500
I am fairly new to cryptography, though with a good math background, and
have several questions:
(thank you in advance for your time)
my goal: learn as much as I can in order to, eventually, write decent
cryptographic algorithms or at least be able to thoroughly understand them.
1.Do you have to be a good cryptanalyst before you can call yourself a good
cryptographer?
2.Do you learn by practicing with breaking codes? Can you break codes
"theoretically"?
2a.Where can you find material to work on? (if you need to do so, but I
strongly believe you do)
3.What classic textbooks are a good source of practice problems?
4.If you really want to crack difficult chipers mustn't you possess
excellent programming tools/skills?
5.My user name is the encryption of my dog's name. Isn't this a rather
stupid problem? Anyway, does it make sense to ask you what my dog's name is?
Will your answer tell me if you are a good cryptanalyst (I'm sure you'll say
"no"!)? DO you need to know the algorithm that I used to encrypt it?
6. Am I the only one that doesn't particularly love "applied cryptography,
2nd ed."?
Thank you for your advice and for telling me how to put my hands in to all
this.
Kwd (this is my name encrypted with the same algorithm....)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New unbreakable code from Rabin?
Date: 20 Feb 2001 18:25:06 -0800
Haven't seen any detailed information, but a paper by Christian Cachin
and Ueli Maurer from Crypto 97 seems to have a similar result:
Unconditional Security Against Memory-Bounded Adversaries
Abstract
We propose a private-key cryptosystem and a protocol for key agreement by
public discussion that are unconditionally secure based on the sole
assumption that an adversary's memory capacity is limited, while no
assumption about his computing power is made. The scenario assumes that a
random bit string of length slightly larger than the adversary's memory
capacity can be received by all parties. The random bit string can for
instance be broadcast by a satellite or over an optical network, or
exchanged over an insecure channel between the communicating parties. The
proposed schemes require very high bandwidth but can nevertheless be
practical.
Here we have the same two elements: provable security and an assumption
of an adversary with limited memory.
The Caichin/Maurer paper presents a potential realization which is on
the verge of being practical. Assume the existence of a 16 Gbit/s
satellite channel that is used for one day, making a total of 1.5 E15
bits. Assuming that the adversary can store no more than 100 Tbytes,
8.8 E14 bits, this will exceed his memory.
The parties share an initial secret key of 102 bits. They use this to
randomly select a shared hash function that will serve as an index
into data stream, and they sample about 1.7 E9 bits (200 MBytes).
However, with these parameters the adversary potentially has
information about some of these bits, so the parties go through a
privacy amplification phase (essentially they hash their shared bits).
The authors show that they can extract 6 MB of virtually secret
information. The adversary knows not more than 1E-20 bits with
probability about 1E-4. The 6 MB of data can be used directly as a
one time pad, for example.
Perhaps the Rabin result improves on these figures, or uses a
different security model. It is curious that it is getting so much
attention when previous results are known for what seems to be a
similar problem. Perhaps the newspaper story misrepresents the novel
aspect of the results.
Alpha
------------------------------
From: "LeeJ" <[EMAIL PROTECTED]>
Subject: SIX FIGURE SALARIES
Date: Tue, 20 Feb 2001 21:42:26 -0500
Do you need extra cash?
Work at home 10-15 hours a week around your schedule. No up-front money
required. Earn $500-
$1,000 part-time or $2,000-$6,000 full time. Full online training is
provided! All you need is a
computer with Internet and email access and a desire to make a change!
Contact: [EMAIL PROTECTED] Subject Line: Email Processors
WORK AT HOME: Be your own boss!!!
Are you ready for something different?
Have you had enough of the daily grind?
Are you tired of watching others profit from YOUR efforts?
Would you like to work at home to allow more time for your family, friends,
or hobbies? Have you
given up on all those dubious offers that promise everything, but leave you
with nothing? ME TOO!!!!
That's why I became an Email Processor. I run the whole business online,
which means I have very
low overhead costs and I can do all my work from the privacy and comfort of
my own home around
my schedule. You can potentially earn $500-$1,000 part-time or
$2,000-$6,000 full time!
Full online training is provided. No up-front money is required. All you
need is a computer with
email access, some spare time, and a desire to change directions in your
life! For more information,
contact [EMAIL PROTECTED] with "Email Processor" in the subject line.
Here is your opportunity to make money, whether it is a second income or
your main income. You can
easily earn $500 per week while spending just 10 hours of your time! You
could even make $2,000
plus if you are willing to devote full time hours. All work is done out of
your own home. All you
need is a computer and all of the online training is provided. It's a free
30-day trial period, so you have
nothing to lose. Start making money today! Send an email to
[EMAIL PROTECTED] with "Email
Processor" in the subject line, and type your name and email address in the
message box.
This business has great potential for those who are willing to work it. If
you looking for a get-rich-
quick plan, keep looking! Interested? Then visit my site and see for
yourself!
How would you like $1,000-$5,000 a month? No start-up money required. We
will train. It's fun,
easy and takes a few hours a day. You set your own schedule. Fully legal
and you'll help people
enrich their lives. If you have a computer and Internet access then you're
ready to start. Contact: [EMAIL PROTECTED] : Subject: SHOW ME.
A HOME WORKER'S DREAM COME TRUE!!!!
Sensational income. Part-time, or full time. No experience or capital
needed. Not MLM. Send email
for "FREE REPORT" to [EMAIL PROTECTED] .
Work at home 10-30 hours per week, part-time or full time. Income based on
time commitment and
effort, averages $2,000-$6,000 or more per month. This is not MLM, and it
does not cost you anything
to start.
This is a legitimate home-based business. All you need is a computer with
access to email, and you
can begin collecting a residual income in just a few short weeks. For more
information, contact [EMAIL PROTECTED] and place "SHOW ME" in the
subject line of your message. You
have nothing to lose
and everything to gain. Your success is our success.
James Lee
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Indicative key generation, encryption/decryption time
Date: Thu, 15 Feb 2001 11:30:02 -0800
I'd recommend www.cryptopp.com he has been kind enough to give up both a set
of benchmarks, and a C++ class linrary that was used for the benchmarks.
Joe
"Adrian Wee" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Hello there,
> I am working on a project that requires encryption and I would like to
> get some indicative time (say for 1 milllion process per second) for key
> generation and encryption/decryption time for some popular algorithm like
> DES, RSA and so on as my system is processing power limited.
> Also, where can I find the codes in C/C++ for popular algorithms?
>
> Thanks
> Adrian
>
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: asking for stream cipher resource
Date: Thu, 15 Feb 2001 11:30:04 -0800
"Anthony Stephen Szopa" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Why? Show us one fact that any of you has ever proven about OAP-L3 that
> brings its theory into question?
For reference please see any news archive and search for Szopa's name,
you'll find plenty of him defending his position through lack of knowledge,
and plenty of people making rightful attacks against his system that he then
proceeds to deny. You'll find people making offers to put money against
money that they can break it. Generally you'll find that Szopa is looked
upon rather unkindly in this group.
Joe
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: question1,2,2a,3,4,5,5a,5b,5c,6
Date: 20 Feb 2001 19:05:40 -0800
"h4jiwk9j" <[EMAIL PROTECTED]> writes:
> 1.Do you have to be a good cryptanalyst before you can call yourself a good
> cryptographer?
It depends what you mean by good cryptographer. Some people say I'm a
good cryptographer. That's not totally meaningless since I think I'm
reasonably good at implementing cryptography programs, so if that's
your definition of cryptographer, ok. If cryptographer means cipher
designer (not just implementer), then yes, I think it's important to
first be a good cryptanalyst. By that standard, I'd deny being a good
cryptographer.
> 2.Do you learn by practicing with breaking codes? Can you break codes
> "theoretically"?
Yes and yes.
> 2a.Where can you find material to work on? (if you need to do so, but I
> strongly believe you do)
Textbooks, conference proceedings, actual systems people are using,
weenie posts from sci.crypt (the last are often pretty useless though).
> 3.What classic textbooks are a good source of practice problems?
Elementary Cryptanalysis, by Abraham Sinkov; Military Cryptanalysis,
by Friedman et al; and so forth. Not a classic: The Code Book by
Simon Singh had an interesting 10-part cipher challenge progressing
from easy to hard problems. It's now fully solved but is probably still
fun to take a crack at.
> 4.If you really want to crack difficult chipers mustn't you possess
> excellent programming tools/skills?
It helps.
> 5.My user name is the encryption of my dog's name. Isn't this a rather
> stupid problem? Anyway, does it make sense to ask you what my dog's name is?
Yes.
> Will your answer tell me if you are a good cryptanalyst (I'm sure you'll say
> "no"!)? DO you need to know the algorithm that I used to encrypt it?
It depends ;-). No I don't think the problem is substantive enough to
measure someone's skill, though if they get the answer right away that
probably demonstrates some talent.
> 6. Am I the only one that doesn't particularly love "applied cryptography,
> 2nd ed."?
It's a useful book that fills an important need. I recommend it highly
but that's different from saying I love it.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Thu, 15 Feb 2001 15:23:11 -0800
Let me see if I read that correctly before I reply, it was a little hard to
follow. You are looking for an encryption algorithm and it's corresponding
inverse where
y = f(x)
where x is the public key, y is the private key and f takes arbitrarily
large amounts of time
You are looking for an algorithm where f() does not exist.
Such an encryption algorithm cannot exist, and for one very simple reason.
Under the assumption that the private key is finitely sized, given an
arbitrarily large amount of time you can brute force the private key. And
you can verify it fairly quickly by encrypting to the (known) public key and
decrypting with the (presumed) private key.
What you are searching for is purely unbreakable cryptography, even OTP does
not qualify (you can given very large quantities of time generate each
possible decryption) under your rules. What we can do is force f() to take
longer and longer times. For example if you use a megabit RSA modulus, f()
will take longer than the time left before the universe reaches it's final
state. Generally that's considered to be more than long enough for any
secrets we may have. In fact right now we as a whole recommend RSA keys a
mere 1024-bits long.
Joe
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Super strong crypto
Date: 21 Feb 2001 03:49:24 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Gwyn's proposal was, when a symmetric key K is about to expire, to
generate a new symmetric key K' and send it encrypted under the old
symmetric key, E_K(K').
I must admit that I don't yet understand the point of this proposal.
Standard practice today is, when a symmetric key K is about to expire,
to generate a new symmetric key K' and send K' using the same channel
(typically secured with public-key crypto) that K was sent over.
Since symmetric keys are assumed to be good for encryption of a huge
amount of plaintext -- say, billions of bytes, for typical modern ciphers,
at a minimum -- the cost of the public-key operation for transmitting
a new key is amortized over many bytes and thus is typically negligible.
Note that current practice is at least as secure as Gwyn's proposal
(and possibly more secure). Moreover, with today's key lifetimes and
cost of public-key operations, I see little reason to prefer one over
the other on performance grounds.
But, if you still want to use Gwyn's proposal, let me mention one
risk with implementing it: chosen-ciphertext attacks are dangerous.
Imagine that the sender transmits some plaintext E_K(P) followed by a
new session key E_K(K'), and the bad guy intercepts both ciphertexts
and prevents them from reaching the receiver. Then, if the bad guy can
mount chosen-ciphertext attacks -- i.e., send a chosen ciphertext and
receive back its decryption -- he can break the scheme. He simply sends
E_K(K') in place of E_K(P); the receiver will decrypt this and treat it
as plaintext, and if the attacker can learn the resulting plaintext,
he learns the new symmetric key and can decrypt all remaining traffic
sent over the session. The attacker only needs to succeed once (due to
the way keys are chained), whereas the defender must stop every attempt.
Anyway, it is possible to implement Gwyn's proposal in a way that defeats
these chosen-ciphertext attacks, but extra care must be taken.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Super strong crypto
Date: 21 Feb 2001 04:18:34 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Douglas A. Gwyn wrote:
>what I am particularly interested in is, *assuming a correct assessment
>of that property*, is there appreciable actual weakness that could
>be exploited in practice, caused by piggybacking the distribution of
>additional key material on the existing channel?
In a separate message, I argued that there seems to be little reason to
use this particular technique, and that implementation is a little tricky.
Nonetheless, in this post let me argue that, if properly instantiated,
your proposal is secure, in some sense made precise below.
It seems to be a fairly straightforward exercise in provable security.
I assume familiarity with the modern theory of concrete security;
for background, see, e.g., [1] (especially Section 5). I warn you:
without the background, this post may be a bit hard to grok.
Let's make your proposal concrete: to send a data packet P, we send
E_K(0||P), then we generate a new random session key K', transmit
E_K(1||K'), and replace K with K'.
I assume that the cipher E_.(.) is (t,2,e)-secure: No adversary that
uses at most t steps of offline computation and makes at most 2 chosen
plaintext/ciphertext queries to the cipher has advantage better than e
at distinguishing the cipher from an ideal (Shannon) cipher. See [1].
I claim that your construction is (t,k,ke)-secure, for all k: i.e., if
it is used to transmit no more than k data packets, then every adversary
(running in time at most t) has advantage bounded by ke.
Proof sketch: The basic idea is to show that, if some magic black box
can break the proposal better than expected, then we can show how to use
the black box to break E_.(.) better than expected, in contradiction to
the assumptions.
Assume the claim is wrong, so that there is some adversary A running
in time t and using at most k chosen text queries that distinguishes
the proposal from an ideal encryption scheme with advantage Adv A > ke.
I prove that there exists an adversary B running in time t and using at
most 2 chosen text queries that distinguishes the cipher E_.(.) from
an ideal (Shannon) cipher with advantage Adv B > e. Then, taking the
converse, we obtain the statement of the claim above.
The proof of the existence of such an adversary B is a straightforward
"hybrid" argument. Consider the encryption scheme S_i, such that
for the first i data packets we use the proposal above, then for the
last k-i data packets we send I_Kj(0||P),I_Kj(0||K'j) where Kj,K'j are
independently chosen (j=k-i,..,k) and I is some ideal cipher. Let d_i
be the advantage of the best adversary distinguishing S_i from S_{i+1}.
Note that S_0 represents an ideal k-packet encryption scheme, and S_k
represents the concrete proposal. Then
Adv <= d_0 + d_1 + .. + d_{k-1} (by a triangle inequality for Adv)
yet Adv A > ke (by assumption) so
d_0 + .. + d_{k-1} > ke (by transitivity)
and hence there must exist some i such that d_i > e (by the pigeonhole
principle). But now the ability to distinguish S_i and S_{i+1} with
advantage > e implies the existence of a way to distinguish E_.(.) from
an ideal cipher I_.(.) with advantage > e, implying the existence of
such a B (you can make this constructive if you like).
I've left many details a bit sketchy, so the above should be viewed not
as a full proof but rather as an argument for the plausibility that such
a proof can be constructed. If you want to spend the time to check the
details, I think (I hope) you'll find that they can all be filled in.
------------------------------
From: [EMAIL PROTECTED] (Niels Provos)
Subject: Re: [release] OutGuess 0.2 - steganographic tool
Date: 21 Feb 2001 04:18:42 GMT
On Sun, 18 Feb 2001 19:14:29 +0100, Mok-Kong Shen wrote:
>The principle of modification of Fourier coeffients is known.
>But could you tell something about the novel ideas in your
>scheme concerning statistics? Thanks in advance.
OutGuess uses a correcting transform to preserve statistical
properties of the cover medium. After applying the transform,
statistical steganalysis is no longer able to detect the presence of
steganography.
OutGuess also accurately estimates the amount of data that can be
hidden safely while still being able to maintain frequency count based
statistics. Additionally, other tests like Maurer's "Universal
Statistical Test for Random Bit Generators" do not show a significant
change after data has been embedded.
You can find a paper on this topic at
http://www.citi.umich.edu/u/provos/cv.html#papers
--
Niels Provos <[EMAIL PROTECTED]> finger [EMAIL PROTECTED] for pgp info
"Gravity is the soul of weight." - Anonymous.
------------------------------
From: "Malcolm Herring" <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Tue, 20 Feb 2001 20:30:15 -0800
The critical point in this discussion has been missed. Even if this method
of encryption is infinitely strong, it is compromised by "... communicating
parties select a running sample from the bit stream pool according to some
agreed-upon rule" - i.e. a key exchange. It is therefore only as strong as
the key exchange system.
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Roger Schlafly wrote:
> > From the NY Times:
>
> Thanks for the pointer. Upon closer examination, this is a method
> that I have seen before, perhaps in this newsgroup -- basically,
> establish a publicly visible stream of random bits, and the
> communicating parties select a running sample from the bit stream
> pool according to some agreed-upon rule, and use that as an XOR
> stream one-time key. The idea is apparently that since the enemy
> cannot store all the "infinite" bit pool, he cannot keep up with
> the communicants, since he doesn't know in advance of analysis
> which of the pool bits need to be recorded.
>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New unbreakable code from Rabin?
Date: Wed, 21 Feb 2001 04:45:16 GMT
<snip>
Isn't this replacing the private key with the establishment of
simultaneity to extreme precision? Reader Ichinin is exactly right.
IMHO there are distribution problems as daunting as with the OTP.
Doesn't this make it unsuited to TCP/IP routing?
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: 20 Feb 2001 20:59:17 -0800
[EMAIL PROTECTED] (David Wagner) writes:
> It seems to be a fairly straightforward exercise in provable security.
> I assume familiarity with the modern theory of concrete security;
> for background, see, e.g., [1] (especially Section 5). I warn you:
> without the background, this post may be a bit hard to grok.
What's [1]?
------------------------------
** 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
******************************
