Subject: RE: The Notes password is not stored in the ID file
I’m responding to this post first because the response is easier. I’ll get to Nathan’s once I’ve had time to follow that link.
My assumption was that the notes client was passing the password through the same hashing algorithm and when it matched, it decrypted the id file.
Most people tend to have assumptions regarding security that are based on typical password-based authentication protocols. With these, the client will send the password or a hash of the password to the server, and the server will then compare against a stored value and accept or reject the authentication attempt. However, when encrypting a credential store, there is very little cause to store and compare, since you can use the decryption process itself to confirm that the correct key was used.
Notes will derive a key from the Notes password, and then use that key to decrypt the encrypted portions of the ID file. If the ID file decrypts successfully, then we know that the right key was used. How do we know that the decryption succeeded? Well, the most common technique involves the padding.
Many ciphers can only be used on data that is a multiple of their “block size” in length. For example, RC2, DES, and 3DES all have block sizes of 8 bytes, and AES is defined to use a block size of 16 bytes. However, most data doesn’t conveniently fall upon onto these boundaries – can you imagine how annoying it would be to send encrypted email if you program refused to send the message until it was the correct length? Therefore, the end of data that is being encrypted is typically padded out to the next block boundary – and an entire padding block is used if the end of the plaintext fell onto a block boundary. In the padding scheme defined in PKCS#5, each byte in the padding block is filled with the number of pad bytes used. With this padding scheme, if you decrypt a message, and the last byte is “0x05”, and the previous four bytes are also “0x05”, then you have a high degree of probability that the decryption succeeded - and you also know how much of the message was padding and can therefore be discarded. Notes doesn’t use PKCS#5 – we predate the PKCS series of specifications by quite a few years – but the same concept applies to the ID file. We decrypt the ID file using a key derived from the password, and if the padding matches and our internal checksums are correct, then we know that the correct password was entered.
I hope that was reasonably coherent. 
"In fact, since the space of possible passwords is substantially larger than the space of possible 128-bit hash values, one could not prove conclusively that one had, in fact, guessed the correct password for the ID file, merely that they stumbled across a collision in the hash function with the correct password. "
It sounds as if you are sayin you could in theory pass an entirely different string of text and come up with the same hash. Is that correct? And if so, I still don’t understand the whole point because you said the hash was not in there - yet now you are talking about hash again.
The function that is used to derive the key from the password involves hashing. The first step involves hashing what could be a 8*63=504-bit long password down to a 128-bit hash. Since there are more potential passwords than there are resulting hash values, more than one password could map to any given hash value. These are what are known as collisions. Those identical hashes would then result in the same decryption key for the ID file. However, cryptographers worry about many threats that are completely impractical in the real world, and this is one of those… at least as it relates to password-derived keys.
dave