Cryptography-Digest Digest #52, Volume #12 Sat, 17 Jun 00 20:13:01 EDT
Contents:
Re: How RSA SecurID tokens work? (Vin McLellan)
Re: Cryptographic voting (zzapzing)
Re: Mixing Xor and Addition (tomstd)
Re: Cryptographic voting (Sundial Services)
MD5 Expansion (Andrew Bortz)
Re: How RSA SecurID tokens work? (Roger Schlafly)
Re: Flattening of frequency distributions (Mok-Kong Shen)
Re: Flattening of frequency distributions (Mok-Kong Shen)
Re: Multiple encryptions (Andrew Bortz)
Re: Encoding 56 bit data ---HELP--- (Andrew Bortz)
Re: equation involving xor and mod 2^32 operations (Andrew Bortz)
Re: MD5 Expansion (tomstd)
----------------------------------------------------------------------------
From: Vin McLellan <[EMAIL PROTECTED]>
Subject: Re: How RSA SecurID tokens work?
Date: Sat, 17 Jun 2000 19:13:47 -0400
tomstd <[EMAIL PROTECTED]> wrote:
> >So if I steal a ACE database I can get access to all the secret
> >seeds? Sweet.
Paul Rubin replied:
> It does seem to mean that Security Dynamics can reconstruct all the
> codes, which isn't so great. That's an artifact of the hardware
> though (no way to put new keys in the device), not the design.
When SecurID cards or key-fobs are purchased, RSA ships the tokens with
an encrypted database of the keys embedded in each token, indexed by the
serial number engraved on the back of each SecurID.
At the buyer's site, the local ACE Admin then assigns each SecurID to
an individual and enters a notation in the ACE/Server database which
binds that SecurID, by serial number, to the user name of an employee or
associate (who is known or identified out of band by the
Administrator;-)
RSA offers is ACE/SecurID customers the choice of having RSA maintain a
secured backup file of the tokens, listed by serial number, and the
token-specific secret keys embedded in those numbered tokens (for
disaster recovery) -- or having that record of token/key bindings
destroyed.
Most SecurID corporate customers apparently request RSA to hold a copy
of that data for them in high-security storage.
Obviously, the records RSA holds do not include any information about
which SecurID token has been assigned to which company employee by the
local ACE Administrator.
RSA also has no knowledge of what PIN was created by the person to
which a specific SecurID was assigned -- or, as is sometimes the case,
what PINs were created and assigned by the ACE Admin. (The choice
between user or Admin-generated PINs is determined by local policy.)
Roger Schlafly <[EMAIL PROTECTED]> suggested another
potential attack on the SecurID:
.> Or find some weakness in the pseudorandom number generator
.> in which info about the secret is leaked in the 6-digit codes
.> that are transmitted.
There is no PRN generator. The token-specific keys embedded in each
SecurID are true random numbers, generated by a radioactive-trace
hardware device.
No two of the 6 million-odd SecurIDs which have been shipped by RSA
have the same embedded key or seed.
As I noted, each SecurIDs generates the series of 6-8 digit token-codes
-- continually displayed on an LCD on the face of the token, and each
valid for either 30 or 60 seconds -- by hashing a (possibly known)
binary representation of "Current Time" and the (shared secret)
token-specific key embedded in the SecurID when it is prepped for
shipment.
While it is, of course, remotely feasible that the ten year-old
Brainard hash used in these SecurIDs is flawed to the degree that an
analysis of the token-codes displayed on a particular token could be
used to reverse the one-way function and reveal the secret key embedded
in a particular SecurID, it seems unlikely.
The SecurID hash has has been widely studied by experts associated with
many of the companies and governments which have adopted SecurIDs. They
seem satisfied that the hash is irreversible (or at least -- to quote
the sort of language typically used in this type of cryptographic
evaluation;-) sufficiently so for this application, given the current
state of the cryptanalytic art.
The Brainard hash hasn't changed over the years. The hash used in the
original SecurIDs brought to market ten years ago is identical to the
hash used in the SecurIDs being sold today.
No known cryptographic weaknesses in the SecurID hash has ever been
reported by cryptographers employed by RSA customers, nor by the
independent cryptographers commissioned by RSA to do periodic reviews of
possible new attacks on the SecurIDs and the ACE protocol.
Needless to say, in any such analyses, it is presumed that an attacker
has full access to and knowledge of the unpublished SecurID hash and the
full ACE protocol.
The SecurID hash (and another unpublished hash, designed by Ron Rivest,
used in the interaction between the ACE/Agents and the ACE/Server) were
created and brought to market in an earlier era, before the advent of a
private-sector cryptanalytic community that dominates public debate
about crypto products today. RSA considers itself bound by commitments
made to customers then by Security Dynamics, when the market demanded
secret algorithms -- but even SDI always insisted publicly that the
"secrecy" of the SecurID hash was not necessary to safeguard the
integrity of the SecurID's output, or the two-factor authentication it
enabled.
By contrast, two years ago RSA published the RSApkc-based protocol
which will displace the classic ACE protocol and invited customer and
public review. RSA has also said that the next generation of SecurIDs
will rely upon Rivest's RC6, one of the widely reviewed AES candidates,
to generate SecurID token-codes.
No one would be foolish enough to declare the SecurID a perfect device,
or to claim that it offers perfect security, but its elegant simplicity
has proven dependable and useful in a wide variety of pre-network and
networked environments, and it has been hosted by everything from giant
Crays to desktop PCs.
When smartcards preempt these hand-held authentication tokens, as they
eventually will, I think many will regret the loss of that simplicity,
where -- with no circuit connection to the net -- it is clear exactly
what the SecurID was doing, and that it is doing nothing more than
that;-)
Predictably, new threats emerged as the market, the technology, and the
Net evolved over the years, and many of them had to be addressed with
modifications in the ACE/Server and the ACE protocol -- but the
integrity of the Brainard hash has never really been considered suspect.
To the contrary, as in most crypto applications, the cryptography itself
sits there like a titanium padlock on a wood shack.
In recent years, the threat inherent in Paul Kocher's landmark work on
DPA and timing attacks on crypto hardware has accentuated, shall we say,
the importance of the user-memorized PIN in two-factor authentication,
and highlighted the importance of making a token-holder aware that he or
she is responsible for both the physical security of the token, and for
promptly reporting the loss or theft of a SecurID to his local security
or network manager.
Beyond that, the fact that many ACE/SecurID installations do not yet
consider it necessary to encrypt the link used to transmit a user's
request for an authentication (and the TCP/IP session that will commence
after the user has been authenticated) remains a troublesome. A one-time
password (the SecurID token-code and PIN combo) effectively blocks
sniffer attacks on the authentication service -- its original design
goal -- but "strong authentication" obviously does nothing to secure the
subsequent session against either eavesdropping or session-hijacking.
For that we need network crypto.
As TCP splicing and (post-authentication) session hijacking emerged as
a threat, Security Dynamics (and now RSA) began to urge its customers to
review their risk analysis and consider VPNs, SSH, or otherwise
encrypted links. Many corporations, however, apparently chose to
install encryption in only limited environments, or not at all. Perhaps
they are waiting for IP6 or PKI. Perhaps (he says hopefully) they are
using a straightforward cost/benefit analysis, with a sophisticated
sense of both the level of threat their network confronts, and the
potential losses they risk. Whatever the case, it remains a cause of
concern for me and other professional paranoids.
(Most commercial VPNs, like most commercial firewalls, do ship with
RSA's ACE/Agent code imbedded in them, so they are SecurID-Ready out of
the box. RSA has a list of its VPN partners at:
<http://www.rsasecurity.com/partners>.)
Hope this is helpful and informative. I've been feeling guilty about
growling at Tom earlier, so you, Gentle Reader, are probably getting
more detail than you bargained for, although the subject line seems to
give fair warning;-).
I've been a consultant to RSA and Security Dynamics for much of the
past decade, so my objectivity should be considered suspect. Questions,
criticism, or other comments are always welcome.
Suerte,
_Vin
Vin McLellan
The Privacy Guild
------------------------------
Subject: Re: Cryptographic voting
From: zzapzing <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Date: Sat, 17 Jun 2000 16:10:20 -0700
I think I have come up with a protocol that
fulfills the following requirements:
1) There is no trusted party. This means that if
anyone cheats, or if any conspiracy of up to
n-1 people cheat, everyone will know it.
2) Everyone can assure that their vote has been counted.
3) The ballot box can't be stuffed without
everyone being aware of it.
4) Noone can figure out how anyone else has voted.
(provided they are not looking over the voter's
shoulder. All bets are off in case of shoulder
surfing)
I assume:
1) Everyone knows the PGP authentication public
keys of everyone else who should be voting,
but of course only the individual voters know
the private part of those keys.
2) Some communications are posted to a bulletin
board that everyone can see. Others are
transmitted by means of an anonymous broadcast
protocol (which I assume exists).
Hint: it uses a card shuffling protocol, which
does not need a trusted party (see my previous
post on card shuffling)
How does it work?
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Subject: Re: Mixing Xor and Addition
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 17 Jun 2000 16:14:14 -0700
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
>
>tomstd <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> It's thought by some that mixing addition and xor operations
is
>> a good idea (and it is) because they are different group
>> operations. This however is not essentially true. It's been
>> pointed out time and time again that the lsb is xor-linear.
>> Well I wrote a program to calc the equalities (a+b) == (a xor
b)
>> for a, b { Z(256).
>Well, from a cryptographic standpoint, mixing addition and xor
is not ideal.
>They are pretty close to each other. In particular:
>
>- In terms of linear cryptanalysis, addition shows some pretty
high biases.
>Apart from the obvious linear relationship in the least
significant bits,
>there are also p=0.75 equations between other bits. xor, of
course, has p=1
>biases in all bits
>
>- In terms of differential cryptanalysis, addition/xor shows
some pretty
>strong characteristics. For both, an input differential in the
high order
>bit gives an output differential in the high order bit with
probability 1.
>For any other bit, it is probability 1 with xor, probability
0.5 for add.
>
>- In terms of avalanche, they are too similar. With a chain of
add/xor
>operations, changes in bits tend to effect the corresponding
output bits,
>and the next couple higher order bits. It is necessary to
build in some
>other mechanism to do avalanche.
>
>That said, the great advantage of add/xor is that they are fast
(at least in
>software). And so, the cryptographer can afford to design in
lots of
>add/xor operations and still have a reasonably fast cipher.
It's not so much as relying on the mixture itself, but as an
added bonus. For example TEA uses the mixture of addition and
xor which doesn't augment the security much it does help.
Similar in style to post/pre whitening.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
Date: Sat, 17 Jun 2000 16:20:50 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Ask any European who remembers World War II what he would think about
"relaxing" requirement #2.
It is necessary to identify who has voted in order to correlate counts
of ballots with counts of voters who supposedly cast them. It is also
necessary that the ballot and the voter cannot be correlated.
The root cause of the problem with electronic voting is that in the end
the records will be magnetic or optical -- with no physical object to
back them up. And it is a simple fact that magnetic or optical records
can be falsified or altered after the fact, much more easily than can be
a warehouse full of paper.
Implicit in any electronic system is that the electronic system has not
been intentionally altered, tampered-with, or compromised by a cunning
individual. But let's face it, in the matters of voting and political
power, "How many millions [of dollars] do you require? Name your price,
two, five ten ... and no one will ever know. Really. Just do it - we
all make lots of money and you get more than your fair share...." Yes,
there are plenty of people who would consider that kind of exchange to
be ordinary business. A voting system has to withstand that.
>zzapzing wrote:
>
> >1. It must be secret ballot
> >2. Voters cannot be identified (by law)
> >3. Voters cannot be deduced from the votes
> >4. Votes must be verifiable (not altered) by anyone
> >5. Voters cannot vote more than once
> >6. The system requires no trust of anyone
> >
>
> I agree but I would relax requirement #2.
------------------------------
From: Andrew Bortz <[EMAIL PROTECTED]>
Subject: MD5 Expansion
Date: Sat, 17 Jun 2000 19:20:29 -0400
In the interest of increasing the size of a MD5 hash, I have been
thinking of a fairly simple method:
1) Calculate the MD5 hash of the data
2) Permute the data, preferable at the beginning, in some small manner
3) Calculate the MD5 hash of the new data, and append to the original
hash
4) Lather, rinse, repeat as necessary/paranoid
It seems as though it would work, and using the 256-bit variant (one new
hash) it would appear as though it yields huge advances in protection,
utilizing the apparent collision-free nature of MD5.
Finally getting the root of my question... Since the hash method in its
entirety will/must be disclosed, it will be possible for attackers to
possibly utilize the two hashes in some attack to reveal the data
originally hashed. My question is, is MD5 secure enough to withstand
giving an attacker a significant statistical peep at the data that was
hashed?
Thanks,
Andrew
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: How RSA SecurID tokens work?
Date: Sat, 17 Jun 2000 16:37:50 -0700
Vin McLellan wrote:
> .> Or find some weakness in the pseudorandom number generator
> .> in which info about the secret is leaked in the 6-digit codes
> .> that are transmitted.
>
> There is no PRN generator. The token-specific keys embedded in each
> SecurID are true random numbers, generated by a radioactive-trace
> hardware device.
> ... As I noted, each SecurIDs generates the series of 6-8 digit token-codes
> -- continually displayed on an LCD on the face of the token, and each
The latter is the PRN generator to which I was referring. That is
what the SecurID token is -- a PRN generator. Maybe the seed is
truly random, but all subsequent token-codes are PRNs.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Flattening of frequency distributions
Date: Sun, 18 Jun 2000 01:48:35 +0200
Guy Macon wrote:
> Thus the attacker knows your frequency distribution flattening
> algorithm and reverses it right before he exploits his knowledge
> of the frequency distributions of plaintexts. You gain very little.
Thus a frequency distribution flattening algorithm that is fixed,
i.e. one that doesn't depend on some secret (key) material, isn't
a good idea. I suggest using a polyalphabetical substitution with
a key or a PRNG with a seed (key). Such a step by itself is
not particularly strong, but it should pass as an acceptable
preprocessing step for a well chosen cipher in my view.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Flattening of frequency distributions
Date: Sun, 18 Jun 2000 01:48:41 +0200
Stefan Schlott wrote:
>
> What about compression? Compression algorithms replace common
> symbols with a short, and rare symbols with a long notation.
> This should flatten your distributions (and reduce the amount
> of data to be encrypted).
> A problem, of course, is the notation of the translation table;
> it will have a well-known format, which might lead to some kind
> of a known-plaintext attack.
A normal compression algorithm doesn't have a secret key, thus
the opponent can decompress just as well as the legitimate
receiver. Thus it adds practically nothing to the difficulty of his
task.What we want is flattening that he can't (or with difficulty)
figure out how to undo in order to recover the original plaintext.
M. K. Shen
------------------------------
From: Andrew Bortz <[EMAIL PROTECTED]>
Subject: Re: Multiple encryptions
Date: Sat, 17 Jun 2000 19:42:12 -0400
In article <8hp1vd$ja4$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> We have some encryption program E, and we use it whenever
> we send messages to each other. E is meant to take any
> plaintext (even non-printable data) and encrypt it, to
> transmit it safely to other sites. E identifies the
> encrypted data with a brief cleartext message at the
> start of it's output, to allow the decryption engine to
> avoid trying to decrypt data that never was encrypted.
> Therefore, anyone that can intercept our messages already
> knows we use encryption program E.
>
> Secretly, we also have another encryption program D. It
> isn't public knowledge, but what we really do is take our
> data files and encrypt them with D. Then we take the D
> output and feed that into E. Programs D and E know
> nothing of each other; each is meant to be used as a
> stand-alone encryption engine. D also appends some
> cleartext at the beginning of it's output, but of course
> E encrypts that so our use of D is *mostly* a secret.
>
> I've heard that this hypothetical case is a bad idea, and
> not just because of any false sense of security. Someone I
> respect tells me that the result is actually LESS secure
> than using either D or E alone.
>
> How can this be?
>
> Let's say that word leaks out that we're using D before we
> use E. Someone uses this knowledge to come up with
> frequency distribution or some other pattern for D's
> output. Perhaps it gives them a minor leg up on what output
> to expect from E. But can the result actually be easier to
> crack than cracking D or E alone?
>
> If you can explain why the answer is YES, then I have
> another related question:
>
> Suppose that D is a home-grown "security by obscurity"
> encryption engine that was never released to the public.
> Therefore it was never given public scrutiny, and it may in
> fact have one or more extreme weaknesses that anyone
> familiar with encryption (except the author) could have
> easily detect, if they got a chance to review the code
> and/or analyze the output. But, the source code is held by
> a few trusted individuals and the "encrypted" output is
> never retained after it's been fed to program E or returned
> out of program E, so there's no way to do frequency analysis
> or anything similar. Does your explanation to the first case
> still fit the second case?
>
> Obviously these cases are all hypothetical and I'm not
If E(D(T)) is somehow parallel to a function F(T) that takes less time
than E(D()) then you have increased security, but not double. If F(T)
takes equal time as E() or D(), you have not changed anything (except
making it slower to decrypt for legitimate users). If F() is less than E
() or D(), then you clearly have screwed up.
Andrew
------------------------------
From: Andrew Bortz <[EMAIL PROTECTED]>
Subject: Re: Encoding 56 bit data ---HELP---
Date: Sat, 17 Jun 2000 19:43:01 -0400
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> In article <8hrnjs$jjt$[EMAIL PROTECTED]>, sarnold_intertrust@my-
> deja.com wrote:
> >In article <[EMAIL PROTECTED]>,
> > tomstd <[EMAIL PROTECTED]> wrote:
> >> In article <8hr2kq$2ii$[EMAIL PROTECTED]>,
> sarnold_intertrust@my-
> >> deja.com wrote:
> >
> >> >This brings to mind a question I have had for some time now;
> is
> >> there
> >> >any point in using a key larger than the data to be
> encrypted?
> >> If there
> >> >is danger in brute-force-searching the key, why not brute-
> force
> >> search
> >> >the plain-text instead? :)
> >>
> >> Did you think that through at all? I hope not.
> >
> >The bit about "brute-force plain-text" was very much tongue-in-
> cheek,
> >but the question -- using keys larger than the data -- still
> makes me
> >wonder. :)
>
> It shouldn't. There are (2^64)! possible ways to permute 64-bit
> blocks... that is way more then 2^64, 2^128 or even 2^256...
>
> Tom
>
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
> The fastest and easiest way to search and participate in Usenet - Free!
>
>
With symmetric encryption, using a key larger than the data is very
useful, as mentioned before. However, public-key encryption by its very
nature allows for trial encryptions of arbitrary plaintexts. Therefore,
if this were using a public-key system, using a public key larger than
the data would simply force an attacker to brute force the plaintext.
Andrew
------------------------------
From: Andrew Bortz <[EMAIL PROTECTED]>
Subject: Re: equation involving xor and mod 2^32 operations
Date: Sat, 17 Jun 2000 19:53:41 -0400
In article <8hqlcf$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
>
> One word of caution: Some programming languages don't implement MOD
> the same way that it is used by mathematicians. Instead, they give
> you the remainder after doing a division. Not the same thing.
>
> This bit me in the bum once when I was implementing a date to day of
> week routine in an embedded system using Zellers Congruence.
>
>
>
>
How does the remainder of division with the modulus any different than
the "mathmatical" implementation?
Andrew
------------------------------
Subject: Re: MD5 Expansion
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 17 Jun 2000 16:59:57 -0700
Andrew Bortz <[EMAIL PROTECTED]> wrote:
>In the interest of increasing the size of a MD5 hash, I have
been
>thinking of a fairly simple method:
>
>1) Calculate the MD5 hash of the data
>2) Permute the data, preferable at the beginning, in some small
manner
>3) Calculate the MD5 hash of the new data, and append to the
original
>hash
>4) Lather, rinse, repeat as necessary/paranoid
>
>It seems as though it would work, and using the 256-bit variant
(one new
>hash) it would appear as though it yields huge advances in
protection,
>utilizing the apparent collision-free nature of MD5.
>
>Finally getting the root of my question... Since the hash
method in its
>entirety will/must be disclosed, it will be possible for
attackers to
>possibly utilize the two hashes in some attack to reveal the
data
>originally hashed. My question is, is MD5 secure enough to
withstand
>giving an attacker a significant statistical peep at the data
that was
>hashed?
>From what I gather you want todo this
A = H(M)
B = H(L(A))
Where M is the original message, L is a linear transform and H
is the hash function.
This is no more secure then the original underlying hash
function and I will show why.
We know that a collision by the birthday paradox will take 2^64
effort against MD5 (since it's a 128-bit hash). However, a
collision in A is sufficient to find a collision in the entire
hash. In otherwords your 256-bit hash can be broken in 2^64
guesses which is far under the birthday paradox limit for a 256-
bit hash.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
** 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
******************************
