Conference rusure::math

        There are severe limits on what kinds of encryption technology
        can be exported from the United States.
        
        What country are you in?  It may even ban the use of
        encryption.
        
        Dan

for password encryption, the usual method is a trapdoor function.
run the original pw through the function and save the result.
to authorize a login, apply the function to the offered pw and
compare to the saved value.  this is what vms and unix do.
this kind of "encryption" can be exported freely from the u.s.,
and most places.  code to do it is available in linux, in c.

i can not think of the guy's name, but a 1995 book, 2d edition in 96,
has lots of code, and an order form for it all on 2 floppies.
there has been a mention of it in the internet discussion group for
crypto since it came out. dorothy demming's book from about 1980
is also good, but does not have code if i recall correctly.
i'll look for the author or isbn tonight if no one else posts it first.

these methods (vms&unix) have the cleartext password on the wire.
if you have cpu power at the user end of the wire, you can use
a challenge response system to avoid transmitting the cleartext pw.

it gets more complicated if you want the user to log in to your system
and it will log him into another.

tell us more details of what the problem and perhaps we can help more.

i think andrew is in great britain and thus mostly immune to
some quirks of american foreign policy.

re .2
    
>i think andrew is in great britain and thus mostly immune to
>some quirks of american foreign policy.
    
    It looks to me that Andrew is in Taipei (Taiwan) and before that South
    Africa and before that France. I think he must be a smuggler of some sort.
    (-:
    
re .0
    
    $64k question: Is the encryption to be reversible?
    
    If yes e.g. for secure transmission of messages then this is strictly
    controlled. You can't give or sell to a customer outside the US
    anything that you can obtain on Digital's network, maybe not at all or
    maybe only after a mountain of paperwork and you are obliged to leave
    your testicles with the Department of Commerce.
    
    You can almost certainly get a public domain implementation of DES - just
    don't get it from Digital but this is thin ice so you should perhaps
    consult your local export people.
    
    If no e.g. for VMS and UNIX style (one way) password encryption then
    this is basically uncontrolled. If VMS then of course you just use
    SYS$HASH_PASSWORD. If UNIX, well, you could always steal the code from
    VMS. If you're after deterring casual browsing then LIB$CRC and friends
    (or the general principles behind CRC) could be helpful. The ALGORITHMS
    conference may have something.
                                     

    P.S. We are currently discussing a tool called PROXY in the HACKERS
    conference (topic 1800). It provides reversible encryption of passwords
    to avoid local storage of plaintext passwords. It may be weak enough to
    be exportable (but as always you have to check!) but strong enough to
    deter casual browsing. If it's a possible solution, speak nicely to the
    author.

in .2 i promised a reference.  here it is.
applied cryptography
bruce schneier
john wiley and sons
ny
0-471-59756-2		for 1st edition i think

    Thanks very much,
    
    	This all seems interesting but heavy. I do not want to get into
    technology export issues. All I was looking for is some kind of simple
    one-way scrambling of numbers, and hopefully some routines that someone 
    might have written to implement the functions necessary for password
    maintenance.
    
    	This is not an application with big security requirements. I think
    that I can even get away with storing the password in plain form in an
    Oracle database, as long as I lock the column.
    
    	Thanks for the information: I'll take it from here.
    
    Cheers,
    Andrew.

I had a similar problem once: I needed to store encrypted passwords on disk, but
I did not want them to look like passwords to anybody who stumbled across the
file.  I only needed one way encryption.

I looped over characters and used shifts and XORs to build a hash integer.  The
result was a pretty random-looking integer.

Like all password trapdoors, this is vulnerable to password guessing.  Unlike
any good one, this was probably vulnerable to an attack based on exhaustive
testing of first or last character, and then working inward.

This was done in Visual Basic, so I have no C code to give you.

    Yes this is exactly what I'm looking for. It occurs to me that half the 
    value in such a random function is that you invented it and no one else
    knows what it is. But if you'd be willing to share your VB code with
    me, it would save a bit of time.
    
    Thanks,
    Andrew.

it would take me hours to locate that code again.

here's the idea, in pseudo-code


integer function trapdoor( string s )

declare integer r 

r = some_pseudo-random_literal_integer_key

for each character in s

	r = r XOR character

	r = ROTATE( r , 1 )	! doesn't matter which direction

trapdoor = r

return



>    It occurs to me that half the 
>    value in such a random function is that you invented it and no one else
>    knows what it is.

I have heard that it is a principle of security systems that you should assume
that your adversary knows everything about your system but the key.


Here are some questions which interest me.  Anyone interested may try to answer
them.  


	What is the best way to recover s, given the output?

	What is the best way to recover s, given the output and the key?

	What is the best way to recover the key?

	How much computation would these attacks require?

	What is the best way to improve the security of this function,
	with minimal increase in complexity?

Another varient on the idea might be to use an existing one-way hashing 
algorithm, that is not 'safe' but produces a 'standard' signature.  The 
algorithm I am thinking of is the CRC32 algorithm.  This is a bit by bit
approach, and quickly gives you a fixed length, defined key/result.

If you wanted to get a bit tricky, the alternatives start becoming things
like:
	1.	pass the bytes through, picking up every first bit, then
		run through again, picking up the second bit, ...
	2.	change the case of a defined set of bytes, ie the first,
		second, seventh, ... (no particular logic implied in the
		case change!)
	3.	seed the computation with a 'seed value' that is none
		'ffffffffxh'
	4.	etc...

The thing of this approach, is that the algorithm is not secret, and the 
result is duplicated for numerous keys, but the algorithm is one-way!

An idea....

    re .9                                                                   
    
    I guess we need to define the conditions a bit more.
    
    Is it assumed that the potential hacker knows the general algorithm but
    not the literal key?
    
    Or knows the general algorithm but not the literal key but has access to a
    black box that implements the algorithm? If so, it seems that pushing a
    string of 32 NUL characters through the algorithm will reveal the literal
    key. (I'm assuming circular rotates over a 32-bit register.) It seems
    further that the literal key can be XORd out of the result after the
    algorithm runs, if you know the length of the password, and this new result
    would be equivalent to running the algorithm with the literal key = 0 (but
    I haven't tested that in code). I think you would want the register
    length in bits not to be greater than the password length in characters.

.11>    I guess we need to define the conditions a bit more.
    
As always.  I had some of this stuff in mind, but was not too explicit in .9, to
avoid stifling creativity.

>    Is it assumed that the potential hacker knows the general algorithm but
>    not the literal key?
    
Assume this first, as a minimum.

>    Or knows the general algorithm but not the literal key but has access to a
>    black box that implements the algorithm? 

Assume this second, since the adversary may be able to do this.  People who
design ATMs and smart cards have had to worry about this.

>   If so, it seems that pushing a
>    string of 32 NUL characters through the algorithm will reveal the literal
>    key. (I'm assuming circular rotates over a 32-bit register.)

Right.  Or even one NUL.  Or even a null string "", if it did not break my code.
Your idea is better than what I had in mind, which was feeding in "A" or
"AAAAAAAA."  Either way, if the adversary can control input and see output, the
key is recoverable.  If the adversary can only see one input and one output,
this will still permit recovery of the key, although the algebra is a bit more
complex.

> It seems
>    further that the literal key can be XORd out of the result after the
>    algorithm runs, if you know the length of the password, and this new result
>    would be equivalent to running the algorithm with the literal key = 0 (but
>    I haven't tested that in code). 

Right again.  I had not thought this through, but had guessed that the key would
get more mixed up in the output.  But what you say looks right to me, based on
the definition of XOR.  And you can just do exhaustive search over password
lengths, if you are in the real world of 6 to 12 characters.

>    I think you would want the register
>    length in bits not to be greater than the password length in characters.

Am I missing something?  I don't see how this helps.  I can still use the
attacks above to determine the key.

Anyway, I think that will lead to too many collisions.  For example, if I am
dealing with passwords of 8 characters minimum, then the register would be only
8 bits or 256 possible outputs.  All the adversary would need is enough tries to
produce all 256 outputs to be sure to unlock the system.

Another question:  Assume the adversary knows the system uses passwords of 8
characters minimum and an 8 bit key.  Assume that the adversary cannot see the
key or the output.  Can the adversary design a minimal set of passwords which
will be sure to unlock the system?  How large is this minimal set?  

I can now see that XOR is the worst possible function to use here.  Even ADD
would be better, since it mixes bits up more.

re .12
    
>>    Or knows the general algorithm but not the literal key but has access to a
>>    black box that implements the algorithm? 
    
    Another possibility (for the record) is that you have access to the
    black box but can only get yes/no answers from it.

>Am I missing something?  I don't see how this helps.  I can still use the
>attacks above to determine the key.
    
    It doesn't help a lot. The difference is that if the register length
    is, say, 32 bits and the password length is, say, 14 characters then I
    can immediately determine that password length from the output and the
    key. As you say, though, it is not much of a saving because I could
    just have looped through password lengths 8..14 (or whatever).

>Anyway, I think that will lead to too many collisions.  For example, if I am
>dealing with passwords of 8 characters minimum, then the register would be only
>8 bits or 256 possible outputs. All the adversary would need is enough tries to
>produce all 256 outputs to be sure to unlock the system.
    
    Actually it's worse than that. With an 8 bit register and knowing the
    key I can immediately supply a password of length 1 that will mung to
    the same output value as the still secret password, regardless of the
    length and content of the password!

>I can now see that XOR is the worst possible function to use here.  Even ADD
>would be better, since it mixes bits up more.
    
    Yeah, I realised that after thinking about it more. The problem is that
    each input bit (from the password) contributes to exactly one output bit.
    
    I believe (without doing exhaustive checking) that it should be
    possible given an output, the register length and the key, to find the
    length of the input and a string of that length that gives the output
    and even under character set restrictions (e.g. A..Z only) to find a
    suitable input - with modest computation i.e. no exhaustive input space
    search. This might not be the original password in all cases but
    obviously it is good enough. [Note that the VMS password hashing
    algorithm itself has some well known alternative password pairs - but
    it has at least been fixed so that, as far as I know, the two passwords
    must be of the same length.]
    
>Another question:
    
    Will ponder.

    Thanks for .9. That's the kind of thing I want to use.
    
    With regards to the later discussion:
    
    	WHY is it reasonable to assume that the cracker knows already the
    general algorithm?
    
    Andrew.

>    	WHY is it reasonable to assume that the cracker knows already the
>    general algorithm?
        
        For one, the cracker can be assumed to be following this very
        discussion. :-)
        
        The cracker can dump the binaries and "decompile" them in his
        or her head.
        
        If you use the OpenVMS SYS$HASH_PASSWORD or the UNIX
        scramble-the-password-into-what-goes-into-/etc/passwd
        algorithm [a variation of encrypting a fixed string using DES
        with a key generated from the password], those are well known
        anyway.
        
        Dan

re .14
    
>    	WHY is it reasonable to assume that the cracker knows already the
>    general algorithm?
    
    Theoretical reasons:
    
    1. paranoia => pessimism
    
    If you can design a system that can't be cracked/is difficult to crack
    under the pessimistic assumption that the potential cracker does know
    the algorithm then it is likely to be at least as secure if the cracker
    does not.
    
    2. obscurity ~=> security
    
    Security through obscurity is false security. Real security comes from
    a system that is mathematically known to be "hard" to crack (where "hard"
    would refer to bodies of knowledge like complexity of algorithms
    in the case of password encryption etc.).
    
    Companies interested in having secure password hashing would
    deliberately publish the algorithm to give honest hackers a chance to
    locate flaws (such as in the algorithm posted a few notes back) before
    a dishonest one does.
    
    Practical reasons:
    
    It will depend on the operating environment.
    
    For challenge/response systems operating in a network environment with
    our cracker as an eavesdropper, it is conceivable that the cracker
    really does not have access to the algorithm. However whenever one of
    the systems is commercially available it can be assumed that a
    sufficiently motivated cracker will be able to get access to the
    algorithm. (VMS, for example, does not even make much of an effort to make
    the kernel code non-readable to users of the system. It would hurt, for
    unrelated reasons, more than it would help.)

  Andrew - did you ever receive any of the EMAIL I sent you?
  (I forwarded a copy of some public domain code I had laying around,
  but it appears you never received it, though the mail didn't bounce..)

  - Jim

>    	WHY is it reasonable to assume that the cracker knows already the
>    general algorithm?

Another practical reason:  With most encryption systems it is much easier to
change the key than the system.  So you can give out many keys to many users. 
If somebody breaks in, and the security is in the key, they only learn one key
and can still not read other messages.  When you change that key (which of
course you do frequently) then they are locked out again.  If the security is in
the system, you must change the system to close the door.

Another theoretical reason:  Most encryption systems leave a trace of some kind.
The clever adversary looks at the output, detects the trace, and deduces the
algorithm.  My algorithm, for example, in real world conditions of short
passwords and printable characters would leave a trace of similar or identical
output bits for many input passwords.  The clever adversary could see this
similarity and deduce my algorithm.

And an historical reason:  Even in wartime it is amazingly easy to learn the
system of an adversary.  Most systems have been exposed through physical or
human contact.  If your adversary knows the literature of your field, then the
kind of system you would use can be deduced.  Any tool or application you once
worked on could give more information.  Your paper trash or deleted disk blocks
might give your system away.  So could traffic between your desktop and your
server.  Or your adversary could just walk up to you or a co-worker at a
conference and start a discussion about such things.

With all these ways of exposing systems, it is reasonable to assume that the
general system has been exposed.

    Jim,
    
    	Yes, I did receive them, and I did mail you back. Did you get my
    mail? I'm sorry I've been a bit pre-occupied with work recently.
    
    Cheers,
    Andrew.