Cryptography-Digest Digest #333, Volume #11 Tue, 14 Mar 00 22:13:01 EST
Contents:
Re: how to introduce hs students to cryptography (David A Molnar)
any free-lance cryptanalysts out there? (drickel)
Re: Decompiling/Tamper Resistent ("Trevor L. Jackson, III")
Re: sci.crypt Cipher Contest ("Trevor L. Jackson, III")
Re: NIST, AES at RSA conference (Bryan Olson)
Re: sci.crypt Cipher Contest ("Trevor L. Jackson, III")
Re: NIST, AES at RSA conference (Bryan Olson)
Re: NIST, AES at RSA conference ("Joseph Ashwood")
new/old encryption technique (Arthur Dardia)
----------------------------------------------------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: how to introduce hs students to cryptography
Date: 15 Mar 2000 01:25:29 GMT
Doug Stell <[EMAIL PROTECTED]> wrote:
> We have had good luck starting with the "what do you do with it"
> approach. For 12th graders, some spy-versus-spy or hacker scenarios
> would whet their interest. From there, you can talk about counter
> measures and how you accomplish the task of protecting things.
This sounds like a good idea to me. Maybe you could present an example
situation, an attack by an eavesdropper, and then have the class take a
step back and ask "what went wrong? and how can we fix it? what do we
need to fix it?"
You probably won't get a very crisp set of requirements from people
seeing the situation for the first time...but it will start thinking in
the right direction. Try to get them to ask questions like "Who is
trusting whom? Why? For how long? To do what? How do they know? What
happens if someone behaves badly?"
For example, if Alice is buying books from Amazon.com,
How does Alice know that she's talking to Amazon.com ?
Does she care if she's talking to Amazon.com, or
will anyplace which fills her book order do?
(i.e. "If it looks like Amazon.com and fills your
book order, but it isn't Amazon.com, does it matter?")
How does Alice know that Amazon.com has the right order?
How does Alice know that Amazon.com has the right address?
How does Alice know her credit card number is seen only by
Amazon.com?
What can Amazon.com do if Alice tries to avoid paying?
If "Alice" tries to avoid paying, how does
Amazon.com know the misbehaving party really is Alice?
What can Alice do if Amazon.com tries to avoid shipping?
what is a receipt for Alice?
who would she show that receipt to?
can Amazon.com deny the receipt?
Not all these questions have answers which can be provided by
cryptography. Some of them do - and after you've asked questions like
this, you can use those questions to motivate digital signatures and
public key cryptography. Then you can go back over the questions to
see which ones can be solved with your new tools, and which can't.
In particular, you can show how a large class of attacks are prevented
by the use of cryptography. This includes not just things like an
eavesdropper grabbing Alice's credit card, but ALSO something like
Amazon.com trying to welsh on an order. In effect, you can
enforce compliance with the terms of the contract by using cryptography!
[Note : there's a hard problem lurking here -- how does Alice get a
receipt for her order from Amazon.com over the network, even if
Amazon.com wants the order but not to give a receipt? This
"fair exchange problem" is outside the scope of two lessons.
You could pick a simpler example, or maybe wait to see if any of the
students points it out. If anyone does, explain that it's a real
problem and that people are _still_ thinking about it, even after 20
years.]
Done this way, it seems you can avoid doing much explicit math. Instead
of focusing on the exact details of RSA or a paper cipher, you focus on
how to specify and then use cryptographic primitives to solve
real problems. This is in the spirit of a neat quote due to Mihir
Bellare (following Erdos) : "A cryptographer is a machine which turns
primitives into protocols."
It's also my favorite part of this field. This is just my personal
inclination, but I can tell you that paper and pencil ciphers would not
have excited me very much as a high school senior (which was not that
long ago). On the other hand, telling me that "You can use cryptography
to stop people from cheating" would have gotten my attention very
quickly.
Then again, this may not work unless the class can has some
intuition for how public key crypto and digital signatures work. That's
why I'd suggest specifying the requirements first and then introducing
the crypto -- but even that may not be enough. It seems worth a try,
though.
Thanks,
-David
------------------------------
Subject: any free-lance cryptanalysts out there?
From: drickel <[EMAIL PROTECTED]>
Date: Tue, 14 Mar 2000 17:43:03 -0800
[EMAIL PROTECTED] is looking for a cryptanalyst
I'm not one, but maybe a few more details (the language of the
text, the approximate date of the text) would be helpful. It
might give a clue about the type of cypher likely to have been
used.
david rickel
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Date: Tue, 14 Mar 2000 21:02:43 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Decompiling/Tamper Resistent
John Savard wrote:
> [EMAIL PROTECTED] wrote, in part:
>
> >In order to protect our intelectual property (software) from decompiling
> >freaks, we need to build our crypto software in a tamper resistent
> >device for our network crypto cards.
>
> You may indeed need to do this to protect software from being copied,
> but you don't need to do it so that you can do encryption securely -
> publicly known algorithms can do this.
>
> Tamper-resistance is sometimes done in industry by putting chips in
> potting compounds; I've heard a substance used by dentists is quite
> good; but I'm not sure that chipmakers offer this sort of thing to
> commercial customers.
Some systems require electronic components (DIPs etc) to be labeled with removable
inks. Once a board is assembled and tested it is sanded and washed to remove the
identifying marks. Then it gets potted and cured. Several companies use this to
discourage reverse engineering. At one we speculated on the possibility of
mislabeling chips and components as was done with tanks (armored vehicles) and copper
(uranium). But the resistance of QA and Field Service quashed the idea AFAIK.
------------------------------
Date: Tue, 14 Mar 2000 21:28:08 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: sci.crypt Cipher Contest
Boris Kazak wrote:
> Adam Durana wrote:
> >
> > You people don't understand, to have a contest, which requires entries to
> > compete against each other, all the entries have to share certain
> > similarities. You can't compare a stream cipher to a block cipher, or a
> > block cipher with a 64bit block size to a block cipher with a 128bit block
> > size. All entries have to be trying to accomplish the samething, and the
> > winner is the entry that accomplishes this "thing" in the best way. Someone
> > who does not know what a block cipher is, probablly won't enter the contest.
> > Plus this is a contest of cipher design, and part of designing a cipher is
> > meeting what is required of the cipher. If there were no restrictions
> > everyone would submit whatever and it would just be a mess of unrelated
> > ciphers.
> >
> > - Adam
> **********************************
> And what about the components of ciphering machinery?
>
> I would like to submit there something that can be called a
> "Proposed Universal Key Scheduler" based on a 64-byte shift register
> and multiplication (mod 2^32+1). This procedure can accept any key
> lengths up to 512 bit and can produce an arbitrarily long sequence of
> randomized subkey bytes (full avalanche, change of 1 bit in key changes
> all subkeys).
If you use 66 bytes the function is trivial, needs no multiplication, and runs at
almost maximum bus speed. The 521/32 LFSR with simple sampling meets all of your
criteria.
>
>
> I would like also to submit there a hash function, also based on
> multiplication (mod 2^32+1). Paul Onions poked several holes in an
> early prototype of this function, his ideas about strengthening have
> since been incorporated. The function is scalable, it can produce
> hashes of any size from 64 bit and up in increments of 32 bit
> (so hash sizes of 192 or 224 bits are possible). This function is also
> capable of producing keyed hashes (MACs).
>
> About block and stream ciphers: I have an idea how one can convert
> Blowfish into an ultra-fast stream cipher. Revisiting the Vernam
> tapes (1000 characters and 1001 characters), we can easily simulate
> 5 arrays of mutually prime lengths in Blowfish's P-box and 4 S-boxes.
> The numbers will be 71, 1019, 1021, 1023 and 1024. 11 bytes of
> Blowfish's subkeys will stay unused, the others can be XORed together
> to produce stream ciphering output:
> B(k) = P(k%71)^S0(k%1019)^S1(k%1021)^S2(k%1023)^S3(k%1024)
> The period of this byte sequence is:
> 71*1019*1021*1023*1024 = 77380915780608 ~ 2^46
> Chances are you will have a message shorter than that before rekeying.
>
> I am eager to look at other submissions.
>
> Best wishes BNK
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: Wed, 15 Mar 2000 02:11:11 GMT
Terry Ritter wrote:
>
> Bryan Olson wrote:
> >There is the seed of a reasonable proposal there: design a
> >cipher with three layers each of a different structure and
> >each somewhat larger than needed to resist all known attacks
> >absent the other layers. This is a plausible approach to
> >defending against unknown attacks and a defensible tradeoff
> >between resources and confidence in security.
>
> That might be a good proposal for a new cipher design. But my
> proposals are not about new cipher designs, but instead address how to
> use the ciphers we already have.
The point is that the composition of three ciphers is a
cipher. The distinction is artificial; it's only in your
mind and not in the encryption function. It makes no sense
to say any cipher a single point of failure while the stack
is not. The set of ciphers contains the set of stacks.
> One goal is to use the ciphers we already have to provide a secure
> system even if we happen to use one or two weak ciphers.
>
> Another goal is to terminate any existing break by changing to other
> ciphers. This requires multiple ciphers.
As previously pointed out, changing ciphers does not
terminate breaks - it only limits the quantity of
ciphertext. Attackers can work on any of the ciphers
for as long as they want. Real traffic is redundant,
so the level of protection tends toward the weakest
system.
> >But the proposals I've seen from Ritter are for the
> >arbitrary, or even random composition without regard to the
> >internals of the individual ciphers. What matters is the
> >structure of the cipher we actually use, not whether we
> >choose to view it as one cipher or three. We we want a
> >cipher that will resist future breaks of certain classes of
> >ciphers, then we should choose these layers because their
> >functions are fundamentally different, not because they were
> >once packaged separately and given different names.
> That does
> leave open the possibility that essentially similar ciphers might have
> different names and would be used. Of course each of the ciphers in a
> stack would have different keys, so the issue is not one of a possible
> weakness of composition, but instead the extent to which multiple
> ciphers protect against attack.
>
> In my experience, real attacks are customized against particular
> ciphers, not classes of ciphers.
Look at differential cryptanalysis. It's applicable to
a wide variety of ciphers, and even hash functions.
> Perhaps you would be so kind as to
> give an example of a practical attack other than brute force which
> works in general against, say, any Feistel cipher.
An absurd point for several reasons. First, if the
inability to "give an example of a practical attack" implies
we don't need to worry about them, then the whole thing is
moot, since we can't name an attack that works against,
say, Blowfish. Second, if there's one example of a
construct without a general weakness, that in no way means
that a few arbitrary instances should resist any attack.
Third, in the case of Feistel ciphers we know that simple
round structures can generate the alternating group, and
that in the super-polynomial model of tractability, the
existence of one-way functions implies the existence of
Feistel ciphers without tractable breaks. A general break
of the Feistel construct would therefore imply a break of
essentially all the structures we use in symmetric ciphers.
I find it somewhat amusing that the one person from whom
I've read worries about a general attack on Feistel ciphers
has also ridiculed the very possibility of a general attack
on all complexity-based ciphers. That person is of course
you, Mr. Ritter.
> >> The issue is not *my* favorite encryption function, the issue is
> >> *your* favorite encryption function: Whatever "simpler, faster"
> >> function you like can be one of the three ciphers in a cipher
stack.
> >
> >The issue is encryption function we use. A cipher stack is
> >a cipher. If we can call a cipher a single point of failure
> >without consideration of its internals, then the Ritter
> >cipher stack is also a single point of failure.
>
> Just as there can be no proof of strength for a cipher, there is also
> no proof of strength for a cipher stack. But that hardly means both
> cases have the same probability of weakness.
You missed the point. A an instance of cipher stack _is_ a
cipher. Is the single cipher designed with three sections,
each strong enough to resist all known attacks a "single
point of failure". If so, then so is the stack. If not,
then your logic is in error from the beginning where you
assumed any individual cipher is a single point of failure.
> We have all learned about attacks on ciphers, yet I am unaware of many
> attacks that will succeed against ciphers when they are used in a
> multiciphering stack. Any such attacks will have to make do with far
> less information than is available when a single cipher is used alone.
You are also unaware of attacks which will succeed against
Blowfish. The issue is not attacks of which we are aware.
In any case, a single cipher designed so its sections should
not fall to the same sort of attack should be at least as
good as one in which the sections are choose simply because
the designers once packaged them as different ciphers.
>
> >> In practice, that stack will be at least as strong as your cipher.
> >
> >And the square of Terry Ritter can make the same argument
> >with the same force to justify a stack of three of Ritter's
> >stacks.
>
> The point of a 3-level cipher stack is to provide security while using
> one or even two weak cipher designs. It is true that this solution
> does not provide security if we use three ciphers which are so weak
> that they can be attacked in the stack.
>
> But since you have previously questioned the entire concept on the
> basis that current ciphers are strong enough, it does seem rather
> strange for you to now be suggesting that *all* the ciphers in a stack
> may be weak. Any cipher you think is strong can be present in the
> stack, and you could demand that cipher be used in every cipher stack
> your system negotiates.
You didn't understand my position. For any tradeoff we
choose between resources and safety, we can do better with a
single carefully designed cipher than with your stack.
> >Dan Bernstein is correct: the distinction between building
> >ciphers from simple operations and encryption functions from
> >ciphers is artificial.
>
> A distinction is hardly artificial when all practical attacks apply
> only to one side of the distinction.
Which is not the case here. If we design a layered cipher
following the "reasonable approach" I described above, your
stack of three might result in the very same encryption
function. The fact that you view yours as three ciphers has
nothing to do with what attacks will work. On the other
hand, the fact that you choose three arbitrarily, where the
single cipher is designed so the layers are radically
different, suggests that the designed approach should do
better at resisting unknown attacks.
[...]
> >The significant issue is the structure of one's
> >favorite cipher, not the fact that we can always make it
> >more complex by adding stuff.
>
> I would agree with that, except that I think it is intended to imply
> more than it says.
Of course. In response to Dan Bernstein, you actually wrote:
> >> The issue is not *my* favorite encryption function, the issue is
> >> *your* favorite encryption function: Whatever "simpler, faster"
> >> function you like can be one of the three ciphers in a cipher
> >> stack.
Given this new stack of three, we can still make a simpler,
faster function with at least as good a case for security.
Your claim is like a child's boast that he can name a higher
number than anyone else, provided he gets to go last.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Tue, 14 Mar 2000 21:29:50 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: sci.crypt Cipher Contest
wtshaw wrote:
> In article <aVRy4.5079$[EMAIL PROTECTED]>, "Adam Durana"
> <[EMAIL PROTECTED]> wrote:
>
> > You people don't understand, to have a contest, which requires entries to
> > compete against each other, all the entries have to share certain
> > similarities. You can't compare a stream cipher to a block cipher, or a
> > block cipher with a 64bit block size to a block cipher with a 128bit block
> > size. All entries have to be trying to accomplish the samething, and the
> > winner is the entry that accomplishes this "thing" in the best way. Someone
> > who does not know what a block cipher is, probablly won't enter the contest.
> > Plus this is a contest of cipher design, and part of designing a cipher is
> > meeting what is required of the cipher. If there were no restrictions
> > everyone would submit whatever and it would just be a mess of unrelated
> > ciphers.
> >
> Trying to pick a winner depends on your criteria for winning.
The criteria for winning are encoded in the scoring mechanism. If you give points for
cracking submitted ciphers as well as for submitting uncracked ciphers you'll have
something approximating reality.
> I think the
> more the merrier if it encorages some to try to write ciphers who have not
> tried before. Too bad for those that like everything in order. Neatness
> is not the sole measure of value. Trying to discorage the creative spirit
> or believing that all must approach things the way you do is nonsense,
> although many pretend to have a formula for creativity....be like them.
> --
> Imagine an internet on an up and up basis, where there are no subversive techniques
>to rob a person of their privacy or computer
> functionality, no hidden schemes used to defraud anyone. :>)
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: Wed, 15 Mar 2000 02:20:58 GMT
Terry Ritter wrote:
> "Joseph Ashwood" wrote:
> >Except that in this circmstance it is often necessary to
> >negotiate the cipher-stack, giving an adversary an
> >opportunity to influence the stack choices.
>
> Q: Just how would an adversary have any opportunity to "influence"
> cipher-stack choices?
>
> Negotiation should occur under cipher, presumably a different cipher
> or ciphers than used for the data. So the adversaries would have no
> more opportunity to influence such negotiation than they would have to
> change the plaintext in an acceptable manner. Both situations are
> easily detected with message authentication.
Yes, it can be detected with message authentication. But
what does that have to do with negotiation occurring under a
cipher? A cipher is secrecy mechanism, and does not imply
authentication.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Date: Tue, 14 Mar 2000 18:50:45 -0000
I was not in any way attempting to state that a cipher
offered authentication. If you look at PKCS #1 you will find
that it had to be rewritten for just such a reason.
Let's take a fairly simple case (where I am making up all
the numbers, and haven't done any math).
Using addition mod 26 as a cipher (because I can compute it
easily)
Original plaintext: abcdefghijklmnopqrstuvwxyz
Original Key: zyxwvutsrqponmlkjihgfedcba
Ciphertext: aaaaaaaaaaaaaaaaaaaaaaaaaa
New Plaintext: someworthlessstuffImadeup
New Key (which I substitute for the original key):
something, it exists, I just didn't feel like computing it
New Ciphertext: aaaaaaaaaaaaaaaaaaaaaaaaaa
By having a person sign the ciphertext, based on them seeing
the original plaintext and key, I can substitute my new
plaintext, and no matter what signature scheme you use, I
can forge a message. If you instead sign the plaintext, I
must attack the signature scheme instead of the cipher or
the signature.
Joe
"Bryan Olson" <[EMAIL PROTECTED]> wrote in message
news:8ams27$nnt$[EMAIL PROTECTED]...
> Terry Ritter wrote:
> > "Joseph Ashwood" wrote:
> > >Except that in this circmstance it is often necessary
to
> > >negotiate the cipher-stack, giving an adversary an
> > >opportunity to influence the stack choices.
> >
> > Q: Just how would an adversary have any opportunity to
"influence"
> > cipher-stack choices?
> >
> > Negotiation should occur under cipher, presumably a
different cipher
> > or ciphers than used for the data. So the adversaries
would have no
> > more opportunity to influence such negotiation than they
would have to
> > change the plaintext in an acceptable manner. Both
situations are
> > easily detected with message authentication.
>
> Yes, it can be detected with message authentication. But
> what does that have to do with negotiation occurring under
a
> cipher? A cipher is secrecy mechanism, and does not imply
> authentication.
>
> --Bryan
> --
> email: bolson at certicom dot com
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: Arthur Dardia <[EMAIL PROTECTED]>
Subject: new/old encryption technique
Date: Tue, 14 Mar 2000 21:59:31 -0500
I was sitting around just thinking and general and I came upon ROT-13.
My understanding is that each letter is replaced with one that is 13
letter's ahead of it - resulting in a rather weak cipher. However, what
if you generated a random number and broke it down into 2 digit groups.
Then, on the plaintext performed ROT-XX where XX is the first group,
succeedeed by another ROT-YY where YY is the second group, until you
reach the end of the random number. How secure is this, assuming you
have a good RNG?
Example:
685340725658 grouping
68 53 40 72 56 58 mod 26
16 01 14 20 04 06 final
groups
perform ROT-16, ROT-1, ROT-14, ROT-20, ROT-4, ROT 6.
One flaw is that by grouping only be 2 digits numbers, you only have 99
possible keys, would grouping three terms increase the safety? Either
way, it ends up being that there are 26 different ways to perform the
letter substitution. Maybe the first digits of the random number (which
would be your key) could tell how many numbers should be in each group,
non-inclusive of the beginning digits that give this information.
Any ideas/suggestions?
--
Arthur Dardia Wayne Hills High School [EMAIL PROTECTED]
PGP 6.5.1 Public Key http://www.webspan.net/~ahdiii/ahdiii.asc
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
