Cryptography-Digest Digest #692, Volume #13 Thu, 15 Feb 01 14:13:01 EST
Contents:
Re: A Chosen-Plaintext Attack on a simple Dynamic Transposition Cipher ("John A.
Malley")
Re: National Security Nightmare? (Mok-Kong Shen)
Re: Steganography with ASCII text files (Mok-Kong Shen)
smartcards (Andrew N Armstrong)
Re: Key Exchange (John Myre)
Re: speed vs security (John Myre)
Re: 448 bits Hash algorithm (John Myre)
Re: TLS record compression (John Myre)
Re: TLS record compression (Jerry Coffin)
Re: speed vs security ("Sam Simpson")
How to build SRP under Win32? (Rob Yampolsky)
Re: National Security Nightmare? ("Sam Simpson")
Re: smartcards (John Myre)
Re: asking for stream cipher resource ("Douglas A. Gwyn")
Re: Indicative key generation, encryption/decryption time (Mike Rosing)
Re: speed vs security ("-")
Re: A Chosen-Plaintext Attack on a simple Dynamic Transposition Cipher (Mike
Rosing)
Re: Super strong crypto ("Douglas A. Gwyn")
Re: TLS record compression ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: A Chosen-Plaintext Attack on a simple Dynamic Transposition Cipher
Date: Thu, 15 Feb 2001 07:26:00 -0800
John Savard wrote:
>
> On Thu, 15 Feb 2001 01:42:28 -0800, "John A. Malley"
> <[EMAIL PROTECTED]> wrote, in part:
>
> >Suppose Eve can get as many plaintext blocks P_i(n) as she wants, all
> >encrypted with the SAME permutation PI_(n).
>
> Of course, one of the basic features of Dynamic Transposition is that
> every pseudorandom sequence of transpositions is different, chosen
> randomly for each message.
Agreed. This chosen-plaintext attack relies on Eve getting multiple
messages of her own selection encrypted by the same key sequence. In
practice Alice and Bob should not reuse the same key across two or more
messages. BUT, just how risky is the use of a repeated key? We can
compare and contrast the result with a chosen plaintext-ciphertext pair
for a One Time Pad - Eve can determine the key of the OTP with a single
pair of plaintext-ciphertext. The chosen plaintext attack on the simple
DT required N/2 + 1 chosen plaintext-ciphertext pairs.
We see how the security of the simple DT in the cryptanalysis "erodes"
with key reuse verses the catastrophic "collapse" of the OTP in the same
situation.
>
> Yes, sending balanced blocks with a pattern like
>
> 11110000, 11001100, 10101010
>
> lets one identify the permutation used for them. But security of the
> permutation against that kind of attack was never claimed,
The chosen plaintext enciphered with DT is of the form M | ~M which
satisfied (AFAIK) the requirement for bit-balancing a block prior to
application of the uniformly selected at random permutation to the
block. There's a slight error in the patterns shown above - it would be
these bit-balanced patterns that are enciphered by the same permutation:
11110000, 11000011, 10100101
> and the
> need to make such an attack impossible is (for other reasons as well)
> a requirement for proper use of the cipher. So DT is in no way
> diminished by this attack.
The chosen-plaintext attack illustrates how we can bit-wise logically
combine generated ciphertext out of the simple DT into new ciphertext
for which Eve never provided any plaintext input, but Eve knows what the
plaintext *should be* to generate that new ciphertext. The new
ciphertext corresponds to particular characteristics of plaintext Eve
exploits to map out the hidden permutation applied. AFAIK any DT cipher
exhibits this behavior.
Isn't this an interesting feature of the attack? Can we exploit this
feature of with a single pair of plaintext-ciphertext and with
ciphertext-only attacks? Maybe others can take this observation farther.
If we can't get any farther in these other attacks then we show
quantifiable results as to the strength of a (simple) DT cipher.
Negative results are as informative as positive results :-)
Returning to the bit-balancing method used in the simple DT model in the
OP:
Are there more requirements on the bit-balancing mechanism than just the
original one posted in the group? Are there restrictions on how Alice
and Bob bit-balance a block before permutation? These are important
facts to work out and make clear about the DT cipher.
For example, I think the chosen-plaintext attack shown cannot pinpoint
the exact permutation used when Eve feeds bit-balanced blocks like these
through the simple DT cipher defined in the OP:
11110000, 10000111, 01000111, 00100111, 000101111 ....
where the same bit-balancing block 0111 is appended to the message
blocks 1111, 1000, 0100, 0010 and 0001. One must return to the
cryptanalysis to see if there are other patterns to encipher with the
same key to finally reveal the secret permutation. IMO This kind of
result is important.
If only certain "methods" of bit-balancing prevent the chosen plaintext
attack then it's worth noting them as restrictions on the bit-balancing
of plaintext blocks. We end up "fleshing out" the requirements for a DT
cipher that must be met to ensure its security.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: National Security Nightmare?
Date: Thu, 15 Feb 2001 18:06:09 +0100
John Savard wrote:
>
[snip]
> I suppose one piece of good news is that if I was dumb enough to be a
> terrorist, I wouldn't be smart enough to write my own encryption
> programs.
It is exactly because the terrorists are not to be compared
with the common gangsters that their secrets are hard to
be cracked by the law enforcements. This situation is
getting worse with advancements in crypto, which is the
reason why certain classes of persons wish to suppress
that with diverse means and in all kinds of disguises,
understandably. But that doesn't function well, for the
dark age of all sciences, including crypto, is definitely
forever gone (fortunately or unfortunately).
M. K. Shen
========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Steganography with ASCII text files
Date: Thu, 15 Feb 2001 18:06:14 +0100
Addendum:
Instead of word counts, one can also use (non-balnk)
character counts, or e.g. counts modulo 4 (to get 2 bits
per line).
The stegos may be present only in a part of a document,
which in turn may be among a large number of normal
documents, all preferably to be typed in with a legere
manner.
Without a web publishing site, one can employ e-mails
instead of HTML documents, though the choice of texts
may in general be comparatively more restricted. The issue
of traffic analysis can be non-trivial. One possibility
to be considered could be having a large number of e-mail
addresses that are destined for the same receiver but that
have an adequate amount of normal traffic among themselves.
M. K. Shen
------------------------------
From: Andrew N Armstrong <[EMAIL PROTECTED]>
Subject: smartcards
Date: Thu, 15 Feb 2001 17:07:15 +0000
Reply-To: [EMAIL PROTECTED]
Hi I am Student at Edinburgh University (Scotland) studying
electronics. I am currently in a very short project involving smart
cards aimed at a medical area for storing a patients health records. The
aim of the smart card is to speed up the access to patient records for
Doctors, Nurses, Pharmacists, and Dentists. However this provides a
some problems:
1) The patient records need to be held securely
2) Not all parts of health record should be available to Nurses,
Pharmacist and Dentists
3) There needs to be some way of electronically signing the records.
Allowing changes in the records to be traced back to the relevant
person.
Hence, My main question is about authentication (point 3)and how this
can be achieved. I have limited time to read up on this subject, so I
would be grateful if some one could point me to some reading material
(preferably on the web) which help me understand the main concepts
involved and how it might work in practice. I understand that
authentication involves public and private keys but that is as much as I
know. Also any ideas on how a record could be encrypted and can be read
by a number of people e.g. several doctors, would be appreciated.
If anyone can point me in the right direction or as anybody has any
ideas on the subject it would be very mush appreciated.
Andrew Armstrong
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Key Exchange
Date: Thu, 15 Feb 2001 10:06:25 -0700
Michael Brown wrote:
<snip>
> Trent? Is this a MITM or another Eve?
"Trent" is a trusted third party (i.e., a good guy). In
real life this usually means a (presumably) secure server,
such as the Kerberos authentication server.
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: speed vs security
Date: Thu, 15 Feb 2001 10:19:34 -0700
Simon Hunt wrote:
>
> Take a look at RC5 - it's the most efficient algorithm we've ever seen.
On what platform(s)? What other algorithms have you seen?
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: 448 bits Hash algorithm
Date: Thu, 15 Feb 2001 10:16:11 -0700
Marc Chapleau wrote:
> is there any 448 bits one-way hash algorithm around?
How about SHA-512? (truncated to 448 bits, of course)
JM
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: TLS record compression
Date: Thu, 15 Feb 2001 10:29:53 -0700
Bryan Mongeau wrote:
<snip>
> Is there any disadvantage to compressing after encryption?
<snip>
The main disadvantage is that the compression won't usually
compress, since the ciphertext looks random (assuming adequate
encryption).
JM
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: TLS record compression
Date: Thu, 15 Feb 2001 10:39:32 -0700
In article <jpQi6.253133$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> Is there any disadvantage to compressing after encryption? If not, why
> isn't it commonplace?
As a rule, if you compress after encrypting, your compression either
won't do any good, or else your encryption is pretty lousy.
Compressing first often makes it more difficult to find known
plaintext to use in cryptanalysis -- a small change early in the file
can cascade, making more or less arbitrary changes throughout the
entire file. Generally speaking, you'd prefer that the final phase
of the compression be some sort of Huffman encoding, but in practice
the exact form of compression only rarely makes much real difference.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: speed vs security
Date: Thu, 15 Feb 2001 17:42:58 -0000
On what platform?!?!!?!?
--
Regards,
Sam
http://www.scramdisk.clara.net/
Simon Hunt <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Take a look at RC5 - it's the most efficient algorithm we've ever seen.
>
> Simon.
>
>
> "-" <[EMAIL PROTECTED]> wrote in message
> news:FCLi6.21639$[EMAIL PROTECTED]...
> > Hi
> >
> > does anyone know of any books or sites that compare the different speeds
> and
> > performance of various encryption algorithms? I'm writing an app for
Palm
> > OS, and I've implemented the blow fish 2 algorithm but it's just *way*
too
> > slow.
> >
> > I'd appreciate any pointers.
> >
> > dylan
> >
> >
>
>
------------------------------
From: Rob Yampolsky <[EMAIL PROTECTED]>
Subject: How to build SRP under Win32?
Date: Thu, 15 Feb 2001 12:46:37 -0500
Has anybody out there been successful in building SRP under Win32?
Preferably under VC++?
I'm actually trying to build tinysrp (a subset of the whole srp
distribution). Already buit a client and server on AIX using the srp
stuff out of tinysrp, and now want to build the client under Windows,
but don't think the traditional ./configure script will work there (even
if I install all the Cygwin stuff?).
Anyway, it'd be really nice just to find a config.h file that makes it
work.... Barring that, any help would be appreciated. I'm trying to
link it just what I need statically.
While I'm at it, I'm also planning to use the libdes stuff from OpenSSL
in my Win32 client. There are instructions on building the whole
OpenSSL shebang under VC++, but I'm lead to believe from the libdes
documentation that that subset is pretty straightforward C code that
should build just about anywhere. If you can stop me from spinning my
wheels in advance, that'd be much appreciated too.
Thanks,
Rob Yampolsky
[EMAIL PROTECTED]
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: National Security Nightmare?
Date: Thu, 15 Feb 2001 17:48:38 -0000
Ouch. If they can mount a passphrase on Scramdisk, then the same attack
could be attempted on PGPdisk with approx. one fifth of the same resources
in approximately the same timeframe.
--
Regards,
Sam
http://www.scramdisk.clara.net/
John Savard <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Wed, 14 Feb 2001 22:30:54 -0800, "Paul Pires" <[EMAIL PROTECTED]>
> wrote, in part:
>
> >This sounds much more likely to me. Considering the prevalence of
password
> >protections and the difficulty in picking a "good" one, they would
probably have
> >much success. Sounds like they are going after Quickbooks and excell, not
PGP.
>
> I'd suggest ScramDisk myself.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: smartcards
Date: Thu, 15 Feb 2001 10:45:55 -0700
Rather than attempting a tutorial on the subject, or pointing
you towards generic reference material, it occurs to me that
you might get some useful pointers from Ross Anderson. See
http://www.cl.cam.ac.uk/users/rja14/
http://www.cl.cam.ac.uk/users/rja14/#Med
I have no affiliation with him; I suggest him because of the
combination of cryptographic expertise, experience with medical
systems, educational affiliation, and physical location.
(Unless, of course, your instructor has already forbidden that
kind of outside help.)
JM
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: asking for stream cipher resource
Date: Thu, 15 Feb 2001 17:45:49 GMT
Anthony Stephen Szopa wrote:
> Why? Show us one fact that any of you has ever proven about OAP-L3 that
> brings its theory into question?
When you first notified this group about OAP-L3 some time ago,
several of us pointed out issues with its "theory" (more accurately,
issues with its claims of security). I don't recall seeing any
reasoned response to them, at least not to the one I raised.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Indicative key generation, encryption/decryption time
Date: Thu, 15 Feb 2001 12:21:38 -0600
Adrian Wee wrote:
>
> 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?
Do a google search for "encryption speed". I got 375,000 hits.
Patience, persistence, truth,
Dr. mike
------------------------------
From: "-" <[EMAIL PROTECTED]>
Subject: Re: speed vs security
Date: Thu, 15 Feb 2001 18:24:51 -0000
thanks to everyone who has contributed to this thread.
I've now got some more blowfish implementations to experiment with and also
examples of the other algorithms mentioned.
I'm still in favour of blowfish because it's a 'proven' algorithm and the
replies on this group all indicated that it's quick enough if implemented
properly, so I think I'll just start from scratch (best way sometimes).
- <[EMAIL PROTECTED]> wrote in message
news:FCLi6.21639$[EMAIL PROTECTED]...
> Hi
>
> does anyone know of any books or sites that compare the different speeds
and
> performance of various encryption algorithms? I'm writing an app for Palm
> OS, and I've implemented the blow fish 2 algorithm but it's just *way* too
> slow.
>
> I'd appreciate any pointers.
>
> dylan
>
>
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: A Chosen-Plaintext Attack on a simple Dynamic Transposition Cipher
Date: Thu, 15 Feb 2001 13:00:13 -0600
"John A. Malley" wrote:
>
> For example, I think the chosen-plaintext attack shown cannot pinpoint
> the exact permutation used when Eve feeds bit-balanced blocks like these
> through the simple DT cipher defined in the OP:
>
> 11110000, 10000111, 01000111, 00100111, 000101111 ....
>
> where the same bit-balancing block 0111 is appended to the message
> blocks 1111, 1000, 0100, 0010 and 0001. One must return to the
> cryptanalysis to see if there are other patterns to encipher with the
> same key to finally reveal the secret permutation. IMO This kind of
> result is important.
>
> If only certain "methods" of bit-balancing prevent the chosen plaintext
> attack then it's worth noting them as restrictions on the bit-balancing
> of plaintext blocks. We end up "fleshing out" the requirements for a DT
> cipher that must be met to ensure its security.
That was an interesting description. It kind of reminds me of a
fourier analysis. In principle, you should be able to feed in any
bit balanced block and use it to help you fill out the permutation
table. It may take more than your optimum N/2 blocks, as many as
2N I'd conjecture. But you should be able to build a matrix of
equations for each input bit which maps to all possible output bits
via the permute table, and then solve for the coefficients of the
permute table.
If you think of the permute table as a matrix multiply, then there are
N set bits out of N^2 total bits. Use N blocks of chosen plaintext
as the input and get N blocks of known cipertext as the output. Then
the permute table is just the inverse of the ciphertext matrix (N bits
x N blocks) times the plaintext. The restrictions are that you have
to choose the plaintext block so that it *does* have an invertable
ciphertext block!
So much for that conjecture :-) The construction you chose does it
with half as many blocks. Maybe there's a connection, but you could
use an "arbitrary" set of N balanced chosen plaintexts and get the
permute table, or your optimal set instead.
Patience, persistence, truth,
Dr. mike
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Thu, 15 Feb 2001 18:09:12 GMT
wtshaw wrote:
> Considering what was in the public eye at the time, it was the best thing
> going, but I was after bigger game long before that, and I was on the
> right track. Too many people forget Shannon, that the amount of
> ciphertext necessary for breaking a cipher is a critical part of strength.
I think it's not forgotten, just the designers don't know how to use it.
Here is a "straw man" block cipher design for you all to analyze:
The last PT block before the unicity distance is reached contains
a newly generated random key to replace the one currently in use.
It's a new form of "chaining" mode, if you wish.
> Surely DES was machined like a Swiss watch, paid for by pilfered gold, but
> as far as yield for complexity, it is too intensive. So, we have lots of
> people that did not stray from its rough pattern of what they see as
> success, and I understand why it is difficult to go too far from the
> beach.
As the earliest public example of a successful modern approach to
encryption, DES has certainly channeled designers' thoughts into
a single direction, witness nearly all the AES candidates. The
original constraints on DES (actually Lucifer) included lack of a
viable key distribution channel, so naturally the system was
designed to continue using the assigned key over and over. Yet
a successful exploit of this supposed weakness has not been
publicly demonstrated.
> ... I know that a sound set of reasonable objectives for highly
> secure systems can be done, not what we have in the internet
> today, nor in most computers.
I still urge you to *publish* such a set of security objectives.
How are people going to learn to do better if nobody is willing
to teach?
> ... Boy, it's a real shame, like I heard on TV last night, that
> so many feel like a solving security problems we have today is
> impossible.
It probably *is* impossible so long as the existing protocols
(including HTTP) must be supported. A real, provable solution
might require something like a capability-based implementation
enforced all the way down to the lowest levels. How do we get
there from here, that is the tough question.
> ... If there is something [the power mongers] cannot control,
> they foster a poor replacement, or ban ...
That's partly right, but it doesn't take a conspiracy to explain
the current situation; normal human stupidity can explain it.
It is not just cryptography that is seized upon by the lusters
after power; other scapegoats include crime, video games, health
care, etc. Whatever they can frighten the public with.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: TLS record compression
Date: Thu, 15 Feb 2001 18:11:42 GMT
Bryan Mongeau wrote:
> I remember reading about compression header vulnerabilities to
> cryptanalysis, ...
The claim is that it can provide a small amount of known PT.
Of course, any modern cipher worth using is supposed to be
impervious to known- or even controlled-PT attacks, so it
doesn't seem (to many of us) to pose a significant risk.
------------------------------
** 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
******************************
