Conference vaxaxp::vmsnotes

   What is the application?

   Do you need a hashing (one-way) scheme, or an encryption (encode-decode)
   scheme?  The latter schemes can be export controlled, depending on the
   effectiveness of the algorthm.  (US residents cannot export encryption
   software to the UK without a license -- it's considered a munition.  I
   have a T-shirt that is an export-controlled munition -- the export laws
   are that, uh, unusual.  In other countries, encryption exportation can
   require an export license, and sometimes even an import license...)

   The hashing algorthym used by $hash_password is a purdy polynomial, and
   could easily be modified to fit in six bytes.  Take a look at the source
   listings, or a computing book such as one of Knuth's series...

   As for uniqueness, consider chopping off two characters of the quadword
   $hash_password results, or XOR or otherwise "salt" the values into one
   or more spots in the remaining six bytes.  (This reduces the range of
   the hash, but this may be entirely reasonable for your needs -- if you
   are limited to six bytes of storage, by definition you drop some of the
   range...)

   I am looking for a hashing (one-way) scheme - thanks for pointing out
   the difference - I was unclear before.

   Where would I find the source listings?  (though I suspect this route
   may be too time consuming)

   The uniqueness of the resultant string is essential - my best option
   at present is to do some experimentation with compressing the
   $hash_password result.

Carol.

   What's the overriding goal here?  It's clear you're looking to
   hash six bytes into six bytes.  Why?  Is this a lookup table?
   Is this a security-related scheme?  (Mention of "encryption"
   points to the latter.  And if it's the latter, you may/will
   want someone with some familiarity with this area to look at
   any scheme, as it's quite easy to introduce security holes...

   Depending on the purpose for the hash, the value may not need
   nor want to be unique.  In the case of the sys$hash_password, it
   likely will not be unique.  The purdy algorythm is both difficult
   to reverse, and provides a relatively even distribution.  In the
   case of a hashing scheme used for lookups, there will almost by
   definition be some number of collisions -- a one-to-one scheme
   doesn't save any space...

   I've seen C language versions of the HPWD module (more recently
   known as [SYS]LGI_HASH_PASSWORD.MAR) from various sources around
   the Internet.  The OpenVMS sources are written in Macro.

   --

   Here's the text version of the Purdy algorythm:

      The hashing algorythm computes computes f(U) = p(U) mod P,
      where P is a prime of the form P = 2^64 - a.  The p function
      looks like X^n0 + X^n1*C1 + X^3*C2 + X^2*C3 + X*C4 + C5.

      As used by OpenVMS, the input U is an unsigned quadword.

      The coefficients used by OpenVMS for C1 through C5 are -83,
      -179, -257, -323, and -363, respectively.  These coefficients
      happen to be prime, but this is not a requirement.

      The above ignores the munging of the source string, username,
      salt, etc., that is used to fold the input into a quadword for
      input into the algorythm.

    Re: .0
    
    Find a copy of Bruce Schneier's 'Applied Cryptography (Second Edition)'
    ISBN 0-471-12845-7 (hard cover) or ISBN 0-471-11709-9 (paper cover)
    This book covers such algorithms, examines their strengths & weaknesses
    and provides free C source code examples.
    
    John.

re .2
    
>   I am looking for a hashing (one-way) scheme
    
>   The uniqueness of the resultant string is essential
    
    This is a contradiction. If the algorithm guarantees uniqueness i.e.
    a <> b => f(a) <> f(b) then by definition you have a two-way scheme
    although this says nothing about the feasibility of actually finding
    a from f(a).
    
    You are going to have to step back and give us the big picture of what
    you are trying to do.
    
    If this is strictly for Digital internal use only and it turns out that
    you do need a two-way scheme then I believe that you will not have a
    problem with export restrictions but as always in this area consult
    your nearest Export Licensing people.

Firstly, thanks for everyone's input.

The bigger picture of what I am trying to do is as follows:

I am working on an application which provides a feeder with badge
numbers on it, and I need to encode the badge number in some way,
such that the original badge number cannot be worked out from the
encoded one, but such that the same badge is always encoded in the same
way.

Hence I need the algorithm to encode 6 bytes into 6 bytes, provide a
unique result, and not be reversable!

Carol.

:The bigger picture of what I am trying to do is as follows:
...
:I am working on an application which provides a feeder with badge
:numbers on it, and I need to encode the badge number in some way,
:such that the original badge number cannot be worked out from the
:encoded one, but such that the same badge is always encoded in the same
:way.

   Ok, we're on our way...  We (I) still need more information on
   the proposed usage of this value...  We also need to know the
   value of the encrypted value, and the implications of disclosure.
   (At least in general terms...)

:Hence I need the algorithm to encode 6 bytes into 6 bytes, provide a
:unique result, and not be reversable!

   Why can't you use eight bytes for the "munged" value?  (There are
   other restrictions and requirements, apparently.)

   What are you planning on doing with the badge number?  (How do you
   propose using this "munged" 6 byte value?  It looks like a password,
   or some sort of verfication...  But your repeated use of "unique"
   makes it sound like you want to decrypt the data at some point.)

   If the "mung" operation is reversable, it's (by definiton) encryption. 
   Unique reversability is one of the characteristics of an encryption
   scheme -- from the encrypted text, one -- with the correct decryption
   scheme -- gets one source text.

   With a badge number as the input into the hashing or encryption scheme
   alone, you have a well-defined set of values, and any scheme you can
   come up with is likely going to fall victim to a brute-force attack --
   particularly if the scheme *is* reversable.  (Some of the more 
   sophisticated -- and export-controlled -- encryption schemes might
   be able to keep the text hidden, but the exportable 40 bit keys can
   be broken in under 4 hours through brute-force attacks.)

   If this is a password or verification, whether or not it is unique is
   not particularly relevent, as long as it is extremely difficult to
   "forge" a value, and as long as you have an "index key" to locate the
   appropriate "munged" value in the database for comparison.

   The OpenVMS purdy polynomial password scheme, for instance, does not
   guarantee a unique "munged" value.  (It was possible in one of the
   earlier versions to add a known sequence of characters to the end of
   the password, and the resulting "munged" value would be the same value
   as the original "munged" password value.)  The two "index keys" in the
   SYSUAF are the username and the UIC values.

   If using a badge number as a verification or as a password, you will
   want to include the "index key" value and/or other attributes (such
   as a random "salt" value), in order to better conceal the "munged"
   value.

re .-1

>   Ok, we're on our way...  We (I) still need more information on
>   the proposed usage of this value...  We also need to know the
>   value of the encrypted value, and the implications of disclosure.
>   (At least in general terms...)

Unfortunately, the answer to most of your questions is that I don't know!

I have been provided with a lot of information from this note, which
should be sufficient to perform the required encryption/encoding - I 
obviously cannot use $hash_password, so will use a look-up table or 
sequence number type of functionality so as to ensure uniqueness.

Once again, thank you to everyone who has responded.

Carol.

re .7,.0
    
    It looks like Carol might have exitted but anyway ...
    
    perhaps the requirement is that data is to be stored and/or transmitted
    against a munged badge number so as to obscure the connection with the
    real badge number. This would require a unique munged value (and, as
    various notes have said, mean that we are talking about encryption
    rather than hashing).
    
    $HASH_PASSWORD is not usable. DES probably is.
    
    I see no reason for the munged value to have to be 6 bytes. I await
    enlightenment. Perhaps the convenience of maintaining a record layout?
    
    Obviously with an input having only 1 million values, brute force would
    probably take only a matter of minutes for the single machine
    horsepower available to most people on Digital's network for most
    encryption algorithms. Some additional information would have to be
    part of the munging.
    
    It sounds to me that the entire data file should be stored and/or
    transmitted encrypted.