Cryptography-Digest Digest #525, Volume #12 Thu, 24 Aug 00 10:13:00 EDT
Contents:
Re: An interesting cryptographic problem ([EMAIL PROTECTED])
Re: Bytes, octets, chars, and characters (Dan Pop)
Re: Serious PGP v5 & v6 bug! (Ron B.)
Re: Serious PGP v5 & v6 bug! ("Michel Bouissou")
Re: Provably secure stream cipher ([EMAIL PROTECTED])
Re: Very Fast Decorrelated Cipher ([EMAIL PROTECTED])
Re: Comment from Hardware Experts Please ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: An interesting cryptographic problem
Date: Thu, 24 Aug 2000 13:27:44 GMT
In article <8o091n$24v$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
[see original posting]
Many thanks for your helpful responses.
Unfortunately the suggested approaches of encrypting the database
information or using stored procedures to implement access control are
not especially easy to implement given that it is extremely desirable
to layer this security system on top of an existing application with
minimal changes to the application code or tables.
At present the approach I am considering (invented yesterday afternoon)
works as follows:-
There is an authentication server running on a machine somewhere which
is reachable via TCP/IP. This server accepts authentication requests on
behalf of clients.
The encryption algorithm is DES in Cipher Feedback Mode. This is a
proven, fast algorithm for which public domain, trustworthy
implementations exist which are free of patent and licensing
restrictions. DES is more than sufficiently secure for this
application, which is not 'mission-critical'. DES in CFB mode has the
advantage that successive encryptions of the same plaintext produce
different encrypted text. This makes dictionary attacks much less easy.
There are two keys, and all encryption/decryption operations are
performed with the two keys. One key is known to the application (the
Application Secret Key (ASK)) and the other is known to the customer
(the Site Secret Key or SSK).
Both keys can be changed at any time though for reasons I will go into
the SSK is easier to change than the ASK.
The reason for having two keys is to protect both parties from each
other. The customer can change the SSK and the application vendor
cannot access it directly, so ex-employees, contractors etc. associated
with the vendor cannot exploit inside knowledge to compromise a
customer's system. Conversely, the customer knows the SSK but does not
know the ASK and consequently a customer system administrator cannot
exploit their knowledge to compromise the system in such a way as to
implicate the vendor. Sure, they can nuke things, but they can't forge
a false trail.
The ASK is embedded as a resource in a file or DLL on each client
machine, and also in a file on the authentication server. The ASK is
scattered across a large amount of pseudo-random data in order to
obfuscate it from casual inspection.
Each client contains a DLL which knows how to extract the ASK from this
file (or has it embedded in the DLL as a resource - the details are
unimportant). The authentication server knows how to extract the ASK
from a server-side file, in the same way.
Although disassembly of the DLL would reveal the key offset positions
and thus permit an attacker to determine the ASK, this is an acceptable
threat. The sole purpose of obfuscating the ASK is to make it
reasonably difficult for the customer to determine its value.
No client contains a copy of the SSK in any form. The SSK exists in
only one place, the authentication server machine. It is placed in a
file and locked down by OS permissions so that only a specific user
account may access it. The AS runs in that account context.
A client wishing to be authenticated accepts logon credentials from its
user {u,p}. It then encrypts p with the ASK and transmits the resulting
tuple to the AS.
The AS decrypts the password with the ASK, and uses a database account
of which it has knowledge to access the RDBMS. (note that account
details can be stored in a protected file on the server in the same way
as the SSK). The database account has limited rights to access certain
tables. In particular,there is a user table on the database which
contains tuples consisting of the following entities
{username,logical_password,physical_password}
The logical and physical passwords are stored encrypted. They are
encrypted first with the ASK and then again with the SSK, then base-85
encoded to render them suitable for storage in a standard varchar()
column.
The logical_password field for the user is retrieved, decrypted and
compared with the decrypted password supplied. If they match, the user
has been logically authenticated. That is, they are recognized as a
valid user of the application.
The physical_password field is then decrypted with the SSK and sent,
still partially encrypted (with the ASK, since the original encryption
used both keys) back to the client.
The client decrypts the physical password field with the ASK and
prepends a fixed string to the user identity to create a new tuple
{u',p'} which it presents to the database. It then has a direct
connection with the database as user u'.
The physical password bears no relationship whatsoever to the logical
password. The user may change his or her own logical password at any
time; the result is accepted by the AS which re-encrypts and stores it.
The administrator may change the physical password at any time using a
vendor-supplied utility. This calculates a random password and then
encrypts it. This password is never displayed to the administrator.
This means that the administrator can set an initial logical password
for the user but cannot know what the user subsequently changes it to.
Nor can the administrator know what the physical database passwords
assigned by the utility are - it will maintain the database logins for
the administrator who can therefore only see that users u1',u2',....un'
exist on the database but not what their passwords are. However, if
there is any reason to believe that system integrity has been
compromised, the administrator can request that any or all physical
passwords are changed; new random passwords will be reassigned to any
or all logins.
The administrator can change the SSK at any time with a supplied
utility. The utility randomly chooses a new SSK, checks that it is not
a known weak or semiweak DES key and then decrypts and reencrypts all
logical and physical passwords based on the new SSK. The administrator
is not made aware of the new SSK, though they might choose to examine
the stored file if they wished.
Recall however that the administrator does not know the value of the
ASK, nor how to retrieve it, so they cannot decrypt anything.
The ASK can also be changed. This involves creating a new ASK file with
a randomly-chosen ASK embedded in it. To avoid attack by differential
cryptanalysis, the new file should also contain a large amount of fresh
pseudo-random data, making it extremely difficult to determine the key
offsets within the file. The new ASK is never revealed to the user.
The client-side DLL or resource file must also be created or patched by
the same utility, which will likewise obfuscate the new key with fresh
random data. The DLL or resource file must then be copied to all
clients.
This approach seems to be reasonably immune from attack. A malicious
system administrator could disassemble the DLL to determine the ASK and
then use this knowledge to decrypt password information - but this is
an acceptable risk. Unless this is done, a malicious system
administrator cannot fraudulantly redirect a user to a different
physical logon or forge a new set of credentials. A malicious outsider,
even a knowledgeable one, cannot access the SSK directly by any means
because they cannot bypass the OS security and access the file
containing the SSK, and the AS will never reveal the SSK.
Therefore, a malicious outsider can at best determine the ASK and forge
a set of credentials to be supplied to the AS. If, however, these
credentials are not valid, i.e the user identity and logical password
don't match, the AS will refuse the request. So the outsider must have
knowledge of a valid {u,p}.
Having then gained access to {u',p'} via this attack, the outsider
still cannot decrypt other {u',p'} since knowledge of the SSK is
required for this. Nor can they forge credentials for some other user
since they can't decrypt the logical passwords. Of course, they can
manipulate the database as u' but the information contained therein is
not particularly sensitive and any changes they make will be audited by
the identity u', making it easy to trace. Unless they have gained
access to administrator credentials, the authority under which u'
operates will be insufficient to permit the creation of new database
users.
The only other thing a malicious outsider can do is redirect the client
to a fake AS. However, this gains them nothing. The fake AS cannot
access the SSK and cannot gain access to the RDBMS so no penetration is
possible.
This system seems to be reasonably immune from any attack I can throw
at it, short of collusion between an insider and an outsider, and even
under these circumstances once the authority to administer the system
has been revoked from the insider, a new key can be defined and the
vulnerability removed.
It is important to subject systems such as this to peer review so if
you can think of any flaws I would be extremely grateful to hear of
them.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Dan Pop)
Crossposted-To: comp.lang.c
Subject: Re: Bytes, octets, chars, and characters
Date: 24 Aug 2000 13:32:14 GMT
In <[EMAIL PROTECTED]> Keith Thompson <[EMAIL PROTECTED]> writes:
>To get back to the topic of the newsgroup, the size of the integer
>registers is *usually* the most appropriate size for type int.
s/is/was
Nowadays, the most appropriate size for type int seems to be 32 bits.
The only exceptions are implementations for chips designed over 20 years
ago, but still in use.
>The
>only reasons I can think of for using a different size are (1)
>compatibility with another, usually smaller, architecture, and (2) the
>integer registers are smaller than 16 bits.
You've missed the most sensible reason: if you were to write a compiler
for a processor with 64-bit registers and no backward compatibility
issues and you made int a 64-bit type, how would you map the 8-bit,
16-bit and 32-bit integers on the C89 standard types?
If you make int a 32-bit type, the solution becomes obvious:
char 8-bit
short 16-bit
int 32-bit
long 64-bit
Dan
--
Dan Pop
CERN, IT Division
Email: [EMAIL PROTECTED]
Mail: CERN - IT, Bat. 31 1-014, CH-1211 Geneve 23, Switzerland
------------------------------
From: Ron B. <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: Serious PGP v5 & v6 bug!
Date: Thu, 24 Aug 2000 13:54:10 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
On Thu, 24 Aug 2000 13:33:30 GMT, "JL" <[EMAIL PROTECTED]> wrote:
>"Ron B." <[EMAIL PROTECTED]> a �crit dans le message news:
>[EMAIL PROTECTED]
>
>> If a business
>> requires this then Jane may have no choice in her business
>> communications.
>
>Then her company shouldn't complain if sensible information is
>compromised. If you don't trust your employees you shouldn't hire
>them in the first place.
>
>JL.
>
This may not be a matter of personal trust. The company may see Jane
as the perfect employee. If Jane is has a heart attack, has a fatal
accident or for other reasons beyond her control is not available to
decrypt important data, the company may have legitmate reasons to
have access to her messages.
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 6.5.3 for non-commercial use <http://www.pgp.com>
iQA/AwUBOaUo8wzUoy7OvTSOEQJPMQCeN/3+kRaow9HEXBOJPjlF6T/VwLgAn0Pu
nQuYnh6+118b1/yntajMHyda
=EKFT
=====END PGP SIGNATURE=====
------------------------------
From: "Michel Bouissou" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: Serious PGP v5 & v6 bug!
Date: Thu, 24 Aug 2000 15:57:40 +0200
Howard <[EMAIL PROTECTED]> a �crit dans le message :
Lv8p5.504$[EMAIL PROTECTED]
>
> I agree that experienced users should be able to spot an ADK quite easily
> at least those who read the manual and spot the Red circle in their
> keyring.
Unfortunately, the world in not made only with experienced users. I agree
that trying to improve one's privacy by using crypto software whithout first
reading *and* understanding the manuals and underlying concepts is stupid
and will not result in good security, but usually in huge mistakes. On the
other hand, it is a matter of fact that quite a percentage of PGP users just
want a 10 minutes training with the major "do and don't" which they will
mostly forget short after.
It's already hard enough to explain to Mr. John Smith the basics of key
certification and signature, for sure you will mess his brain if you start
telling him at once about the complexities of ADKs and the like. Mr. Smith
only wants to get "secure" one-click-away encryption or decryption and
doesn't want any further complexities. Sad but true.
In such a situation, any major flaw in the PGP software that enables an
attacker to forge public keys in a way that he will be able to decrypt
messages encrypted to these keys is really catastrophic.
> However the freeware manual, while telling you how to recognise
> one and set the options to warn you about them, doesn't deal with the
> issue at all.
You're right.
> Michel, can you explain your view that DH/DSS keys shouldn't be used?
It's just a matter of reading end understanding Ralf Senderek's document at
http://senderek.de/security/key-experiments.html . It shows that an attacker
can (for example) download your public key from a key-server, add his own
cooked ADK to it, and start distributing this forged version of your public
key -- maybe even upload this forged version back to the keyservers,
overwriting your legitimate one?
Later on, any of your (uninformed) correspondants that would get a forged
copy of your key (maybe as simply as when using the "update" option of
PGPkeys to check validity of your key and get possible new signatures from
the keyserver) would encrypt any messages for you to the attacker's key as
well, resulting in the attacker being able to decrypt the message.
When decrypting the received message, you may not notice the supplementary
key the message was encrypted to, and thus keep on ignoring that the message
was encrypted to the attacker as well.
Still worse, being able to read the message probably means that the attacker
was able to intercept your e-mail. If the attacker is able of a true MITM
attack, he can remove the message (that he was able to decrypt) and
re-encrypt it to a genuine copy of your key, so you will receive the
original message encrypted to your key only, and have no way to directly
discover the manipulation. Only, of course, that the such re-encrypted
message could not be PGP-signed by the sender.
I'm not myself expert in the PGP packet structure (and so request expert
advice), but could it be possible that the MITM attacker gets the message,
and then only removes the packets corresponding to the additional ADK
encryption before forwarding the message to its intented recipient, thus
keeping the signature intact and making the interception unnoticeable to the
recipient?
Furthermore, you CANNOT have control over possibly forged copies of your
public key circulating around, so you cannot tell when somebody possibly
could use such a forged copy to encrypt a message for you, not only
compromising the content of the message and the sender himself, but possibly
compromising you as well by unwillingly revealing in this message
information that could compromise you, such as quotes of an original message
you sent him, or the like.
For all these reasons, and if this "bug" is confirmed, the only reasonable
and secure choice would be to immediately quit using any key format or
software that might allow an attacker to append its own ADK to one's public
key.
Which unfortunately means quit using any PGPv5 or PGPv6 DH/DSS keys, or
PGPv5 or PGPv6 created RSA keys.
> Aren't ADKs possible with RSA Public keys?
I thought they were not possible, but reading
http://senderek.de/security/key-experiments.html I learnt that I was
mistaken and they seem to be actually possible when the RSA key has been
generated under PGPv5 or PGPv6, because it will then use the v4 signature
scheme that allows it, or even an existing RSA key made from PGP 2.6x (with
a v3 signature scheme that doesn't support ADKs) could be "transformed" into
a v4 one using PGPv5 or PGPv6, which would render it vulnerable to ADKs.
This is my understanding of this part of the document, although the
mechanism that will allow such a transformation from v3 to v4 is quite
unclear to me.
I don't expect RSA v3-signed keys that are simply imported into PGPv5 or
PGPv6 to suddenly change into RSA v4-signed keys, because for this it would
at least need that the key owner resigns the key (and would apparently
result in the key ID and fingerprints to change).
Maybe Ralf Senderek could give better explanations about the way a RSA
v3-signed key could transform into a RSA v4-signed key...?
Anyway, Ralf's advice is to use only RSA keys made by a v3-signing-only
version of PGP, which probably means PGP 2.6.3i or earlier, and to use them
on a PGP version that will not manage DH/DSS keys or ADKs at all and will
reject any RSA key bearing a v4 signature.
This seems to be the "best precaution" choice, although it means that
concerned PGP users would have to quit using the nice recent GUI PGP
versions and revert back to the good'ole command-line DOS versions such as
PGP 2.6.3i (which I have always preciously kept a safe copy with me, just in
case...)
Or replace PGP with GnuPG which, although it manages PGP's DH/DSS keys quite
well, doesn't seem to understand PGP's additional "features" such as ADKs or
supplementary revokers.
> And isn't the default option in
> V5 and 6 set to warn when encrypting to ADKs?
I guess it depends on the *exact* PGP version you are using... It is an
option in PGP 6.5.2freeware "preferences" for example, and I'm not sure it
defaults to "on" as I always check and change PGP preferences to suit my own
needs at installation time...
Actually, using PGP as a personal privacy tool, I've never been personally
confronted with ADKs before, and I was putting my trust into PGP to warn me
if ever I received a key bearing an ADK, by showing the "ADK" ball.... And
you still need to have choosen to have this column displayed in your PGP
keyring...
--
Michel Bouissou <[EMAIL PROTECTED]> PGP DH/DSS ID 0x5C2BEE8F
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Provably secure stream cipher
Date: Thu, 24 Aug 2000 13:47:50 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> [EMAIL PROTECTED] wrote:
> >
> > Here is an idea for a somewhat slow provably secure (as long as the
> > underlying prng is statistically random, but need not wholely
random).
> >
> > Based (yet again) on the simple pair-wise decorrelated function
> >
> > f(x) = ax + b
> >
> > in GF(2^n) (n = 8, 32, 64 ...)
> >
> > The idea is that the prng will make the (a, b) values for each 'x'
that
> > is being encrypted. Since this is pairwise decorrelated and the
values
> > (a, b) are made anew with each output this is provably secure if the
> > stream (a, b) is not guessable (in this case without any known
stream).
>
> Could you please explain 'this' in the phrase 'this is
> pairwise decorrelated'? Further, with the little that I
> (presume to) know about decorrelation, 'decorrelated'
> means a decorrelation (to some order) of zero. Which
> value is zero in the present case? Thanks.
Decorrelated to zero would be f(x) = x, which means knowledge of the
input immediately yields the output.
Decorrelated to one-wise would be f(x) = x + k, where it takes one pair
of inputs and outputs to tell the function from random.
Decorrelated to pair-wise would be f(x) = ax + b, where it takes two
pairs (the inputs (0, 1) specifically) to find the values 'a' and 'b'.
If I give you
f(5) = 5a + b = 23 (mod 256), you have no way of knowing what 'a'
or 'b' was. now if I give you f(4) = 19, you can solve it...
The idea of the stream cipher is to use the pair 'a' and 'b' once per
byte/word making it impossible to solve it. Thus requiring one to
guess the prng state.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Very Fast Decorrelated Cipher
Date: Thu, 24 Aug 2000 13:49:31 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> >
> > To go with my point of precomputed tables I present (source only,
> > paper to follow) a pair-wise Decorrelated 64-bit cipher that
encrypts
> > at 12 cycles per byte on my K6-2 with the reference C code.
> >
> > Please check it out at
> >
> > http://www.geocities.com/tomstdenis/files/tc6a.c
> >
> > The source is relatively easy to follow.
> >
> > I will write a paper soon so please comment.
> >
> > Thanks,
> > Tom
>
> I've a silly question: what were the criteria behind the choice of
> 0x29DF548E as the polynomial?
It's primitive (see below).
> Because the low bit isn't set in the poly, the gf product will have
the
> low bit set iff both multiplicands have the low bit set. This is a
Bad
> Thing. If both halves of the plaintext have the lowest bit clear,
then
> the lowest bit of each half of the ciphertext depends ONLY on the
round
> keys, *not* on the rest of the plaintext.
It was a mistake, there lsb is suppose to be set because the polynomial
made did in fact include a '1' term. My mistake, sorry.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Comment from Hardware Experts Please
Date: Thu, 24 Aug 2000 13:51:18 GMT
In article <8o2e7m$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Guy Macon) wrote:
>
> [EMAIL PROTECTED] wrote:
> >
> >In article <8nvotu$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (Guy Macon) wrote:
> >
> >> I am very concerned aboout your "something close to nlog n steps"
> >> comment. It shows a deep lack of knowledge of hardware/software
> >> tradeoffs that I believe will not allow you to implement a hardware
> >> solution. Going to hardware can only give you a fixed percenage
> >> speedup. It takes an algorithm change to change 2^n to nlog n.
> >> Hardware just does the same old thing faster.
> >
> >Well for starters multiplication in GF(2^n) can be done in n steps
> >easily since all you're doing is adding multiples of one multiplicand
> >via XOR when a bit is set in any position.
>
> Do you believe that whether you do it in hardware or software makes
> a difference in the number of steps?
No, I mean the algorithm only has at least 'n' steps, but in hardware
we can avoid pipeline stalls, agis, etc...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
