help in secutrity features

[Bart Van der Donck]

Michael Wojcik wrote:

[...]

You're wrong twice there. First, there cannot be a "one-way encryption
function", because "encryption" (as a term of art) implies decryption,
which implies a bijection, and so excludes a one-way function. Second,
you clearly claim, in the passage quoted above, that the "irreversible
function" implements an "encryption algorithm", so you did in fact
implicitly claim that there was such a thing as a one-way encryption
algorithm.

As far as I know, in computer science, these words are not clearly
delimited. I think you would agree that the term 'one-way encryption'
is quite widely used. Maybe the meaning is different in stricter
mathematical semantics.

You seem to possess some knowledge about cryptography; yet I find it
strange that you state that decryption always implies a bijection. I
have seen surjective functions as well (in order to retrieve an 'any'
password).

 

[Thomas 'PointedEars' Lahn]

Thomas 'PointedEars' Lahn wrote:
Michael Wojcik wrote:
(It's also likely that they can simply determine the password by
looking at your script. There are ways to prevent that - for example,
by implementing an irreversible function as the verifier - but [...]
It is not possible to prevent the determination of the password; it is only
possible to make it expensive for the cracker. Every encryption algorithm
is susceptible to a brute force key search attack.
I'm not talking about encryption; I'm talking about one-way verifiers.

A verifier includes either a decryption or an encryption algorithm.

That's simply wrong. You clearly do not know what you're talking about
in this case.

Probably the most common password-verification functions today are
based on cryptographic hash functions. They don't use encryption or
decryption algorithms.

A cryptographic hash function is an encryption algorithm, whether you like
it or not.


PointedEars

 

[Lasse Reichstein Nielsen]

A cryptographic hash function is an encryption algorithm, whether you like
it or not.

That would be a matter of definition. I don't have any cryptographic
litterature present (except Wikipedia), so I can't give a reference,
but I would maintain that encryption functions can inverted (i.e., the
encrypted messages can be decrypted) whereas hash functions produce a
fixed size output (i.e., loss of information except for very short
messages).

A cryptographically strong hash function (or a perfect one-way hash
function, if one is ever found) can be used to create an encryption
function, just as an encryption function can be used to create a
hash-function. It just takes further algorithms.

/L

 

[Lasse Reichstein Nielsen]

Michael Wojcik wrote:

[...]

You're wrong twice there. First, there cannot be a "one-way encryption
function", because "encryption" (as a term of art) implies decryption,
which implies a bijection, and so excludes a one-way function. Second,
you clearly claim, in the passage quoted above, that the "irreversible
function" implements an "encryption algorithm", so you did in fact
implicitly claim that there was such a thing as a one-way encryption
algorithm.

As far as I know, in computer science, these words are not clearly
delimited. I think you would agree that the term 'one-way encryption'
is quite widely used. Maybe the meaning is different in stricter
mathematical semantics.

It does appear to be somewhat widely used.
<URL:http://en.wikipedia.org/wiki/One-way_encryption>
It's also correct that it's a misnomer, since it is not really
encryption.

You seem to possess some knowledge about cryptography; yet I find it
strange that you state that decryption always implies a bijection. I
have seen surjective functions as well (in order to retrieve an 'any'
password).

Real encryption should be injective (otherwise it can't be reversed).
An injective function is always surjective (and therefore bijective)
on its image, so in some sense it's always bijective.

A hash function (misnamed "one-way encryption") should specifically
not be reversible, so it's not injective. Whether it's surjective
is again a matter of what one consides its image.

/L

 

[VK]

As far as I know, in computer science, these words are not clearly
delimited. I think you would agree that the term 'one-way encryption'
is quite widely used.

Most definitely. In the Web a rather unique situation was created with
the need to keep user passwords server-side yet prevent password
reading from the server-side database, in case of server data being
stolen. This way in server-side DES usage, like in Perl crypt(), a
password being encrypted but not supposed to be decrypted. Instead on
each login the current encryption result being compared with the
sample encryption result. "one-way encryption" term describes this
pretty well IMHO unless we shall type a whole paragraph description
each time we need to mention it.
That is all aside of DES current security level.

You seem to possess some knowledge about cryptography; yet I find it
strange that you state that decryption always implies a bijection.

I was surprised by this either. Bijection exists only for the most
primitive encryptions like ROT 13 and so. For anything more-or-less
serious there is not any bijection in either way. Unless it some
special cryptographic "bijection" term usage that should be explained
then.

 

[Thomas 'PointedEars' Lahn]

That would be a matter of definition. I don't have any cryptographic
litterature present (except Wikipedia), so I can't give a reference,
but I would maintain that encryption functions can inverted (i.e., the
encrypted messages can be decrypted) whereas hash functions produce a
fixed size output (i.e., loss of information except for very short
messages).

But I do not need decryption for a verifier that uses a cryptographic hash
function. For example, if I store the SHA checksum of a password in
the database, then -- given I use a version of the algorithm that is more
unlikely to cause collisions -- it suffices to calculate the SHA checksum
of any given password and compare the result with what I have stored in the
database to see if the password used is the correct one.

A cryptographically strong hash function (or a perfect one-way hash
function, if one is ever found) can be used to create an encryption
function, just as an encryption function can be used to create a
hash-function. It just takes further algorithms.

Since the password is then not stored as-is in the database, it is stored in
encrypted form there, and hence I think that SHA deserves to be called an
encryption algorithm itself even though it is a cryptographic hash function.


PointedEars

 

[Bart Van der Donck]

Real encryption should be injective

If we assume that the (stored) encrypted string originates from an
unencrypted string (which is the real-world situation), then I think
your statement is true. But an injective function also implies that
there is no guarantee that a decryption is possible (though I'm not
sure to which extent this is relevant to real-world password
encryption).

(otherwise it can't be reversed).

If I understand the terminology correctly, I think this is a logical
fallacy. A decryption does not need to reveal *the* password; the
*any*-password suffices too. The way I see it, encryption then can't
be categorized as injective anymore, but surjective.

An injective function is always surjective (and therefore bijective)
on its image, so in some sense it's always bijective.

Sorry, I lost you here. Bijection is one-to-one, I don't think this is
the case here ?

A hash function (misnamed "one-way encryption") should specifically
not be reversible, so it's not injective.

I agree. I tend to think that the condition for non-reversibility is
to "drop stuff along the route", like "convert to number, multiply by
25, leave out last two digits, multiply by 31". But my cryptographic
training was quite basic only, and long ago

Cheers,

 

[Bart Van der Donck]

Most definitely. In the Web a rather unique situation was created with
the need to keep user passwords server-side yet prevent password
reading from the server-side database, in case of server data being
stolen. This way in server-side DES usage, like in Perl crypt(), a
password being encrypted but not supposed to be decrypted. Instead on
each login the current encryption result being compared with the
sample encryption result. "one-way encryption" term describes this
pretty well IMHO unless we shall type a whole paragraph description
each time we need to mention it.
That is all aside of DES current security level.

I agree with your text, except that this would be a "rather unique
situation" for the internet.

 

[Lasse Reichstein Nielsen]

But I do not need decryption for a verifier that uses a cryptographic hash
function.

True. Nor do you use encryption.

For example, if I store the SHA checksum of a password in
the database, then -- given I use a version of the algorithm that is more
unlikely to cause collisions -- it suffices to calculate the SHA checksum
of any given password and compare the result with what I have stored in the
database to see if the password used is the correct one.

In many situations, the probability of a collision is low enough that
it suffices, yes. Probably most, although some proffesionally paranoid
people would probably not allow any collision to be allowed, i.e., a
"wrong" password to be accepted. They need to store something that
uniquely represent the password.

Since the password is then not stored as-is in the database, it is stored in
encrypted form there,

No, the password is not stored at all. A hash value of it is stored.
Using another hash algorithm, one with less guarantee against
collision (e.g., CRC32, or "mod 32") will only be a difference in
degree, not in kind. It would definitly not be encryption (or safe to
use for that matter).

and hence I think that SHA deserves to be called an
encryption algorithm itself even though it is a cryptographic hash function.

I disagree. Nothing was encrypted.
You computed a value that represents the password, but not uniquely.

It's a great security algorithm, but it's not encryption.

/L

 

[Lasse Reichstein Nielsen]

If we assume that the (stored) encrypted string originates from an
unencrypted string (which is the real-world situation), then I think
your statement is true. But an injective function also implies that
there is no guarantee that a decryption is possible (though I'm not
sure to which extent this is relevant to real-world password
encryption).

If the function is injective, then it is reversible. I.e., for an
encrytion function, e, there exists a *left* inverse, d, such that
for all values, x, that e applies to d(e(x))=x. That's just what
it means to be injective.

Whether it's surjective then depends on what the codomain of the
function is defined to be. E.g.,
The identity function, id(x) = x, is injective. It's surjective
as a function just on natural numbers N->N, but not surjective as
an embedding N->R.

If e is injective on a set M, then it's bijective if restricted to
its own image, i.e., e: M->e(M).

If I understand the terminology correctly, I think this is a logical
fallacy. A decryption does not need to reveal *the* password; the
*any*-password suffices too. The way I see it, encryption then can't
be categorized as injective anymore, but surjective.

I'm not sure I understand the "*ANY*-password" case. Let me try to
see if I am guessing correctly:

We have a function that encodes passwords for accounts and stores the
encoded version. We also have the option of giving an account an
"any password works"-password (traditional Unix passwd it would be
the empty password).

The "any password" code is stored in the same slot as the encoded
real passwords, i.e., the domain of the password field contains any
encoded password and also the special value.

The special value can't be decrypted (at least not to a normal
password, since then it would *be* a normal password that someone
might select, which would be *bad*!).

I guess my point is that you shouldn't talk about decrypting the
special value. You don't decrypt something that wasn't the result
of encrypting.

Sorry, I lost you here. Bijection is one-to-one, I don't think this is
the case here ?

Not in general. The encryption function can be reversed (i.e., has a left
inverse, the decryption function), but the decryption function is not
defined on the entire password field domain.

I agree. I tend to think that the condition for non-reversibility is
to "drop stuff along the route", like "convert to number, multiply by
25, leave out last two digits, multiply by 31". But my cryptographic
training was quite basic only, and long ago

That's a good enough rule of thumb. More precisely, if a function
looses *information*, it is not reversible (that's just saying the
same thing in two different ways). A hash function maps everything
down to a fixed number of bits. That means that any message longer
than that will lose information when hashed (and the pigeon hole
principle tells us that the function can't be injective).

 

[Michael Wojcik]

If I understand the terminology correctly, I think this is a logical
fallacy. A decryption does not need to reveal *the* password; the
*any*-password suffices too.

Decryption must produce the original plaintext. Otherwise it's not
decryption; it's determining a preimage, which is a different operation.

Terms like "one-way encryption" may be commonly used, but that doesn't
make them correct.

In cryptography, "encryption" and "decryption" properly apply only to
functions that are each other's inverse. Cryptographic hashes are not
encryption functions.

 

[Michael Wojcik]

That's a good enough rule of thumb. More precisely, if a function
looses *information*, it is not reversible (that's just saying the
same thing in two different ways).

Yes; information-losing functions are the simple class of one-way
functions.

There are also functions which appear to be computationally one-way:
that is, the functions are relatively inexpensive to compute, but the
best algorithms for reversing them are far more expensive (usually
because they belong to a harder complexity class, so they can be
scaled to be far more expensive). This is the case with the problems
used for asymmetric cryptographic operations: factoring, discrete log,
Hamiltonian path (with specially-constructed graphs), etc.

As far as I know, none of those has yet been proven to be asymmetric
in this way, though eg Hamiltonian path should be as long as P != NP.

All of this is only marginally relevant to the original point, though,
which is that it's possible to verify a password using an algorithm
which does not include the password.

There are even ways to do that so that brute-forcing a preimage is
likely to find a preimage that won't work the next time. The trick is
to expand the password and candidate password using a nonce, so
preimages that collide when mixed with one nonce have a reduced
probability of colliding when mixed with another nonce. Though in the
real world, there are enough restrictions on passwords that this
probably doesn't matter; there may not be a colliding preimage that's
also a plausible password. (Password whitening and expansion can help
with that somewhat.)

 

[Michael Wojcik]

Most definitely.

That doesn't make it correct.

In the Web a rather unique situation was created with
the need to keep user passwords server-side yet prevent password
reading from the server-side database, in case of server data being
stolen.

There's nothing "unique" about this condition. Sensitive data is
sensitive data, and the problem of exposing password secrets long
predates the web.

This way in server-side DES usage, like in Perl crypt(),

Which is taken directly from Unix crypt(), which was around long
before Perl or HTTP.

a
password being encrypted but not supposed to be decrypted.

crypt() does NOT encrypt the password. It encrypts a fixed string
(initially all-bits-zero) multiple times in succession, with the
password as key, using the salt parameter to perturb the algorithm.
The result is not an encryption of the password.

"one-way encryption" term describes this
pretty well

Sure, if you don't care about being correct.

I was surprised by this either. Bijection exists only for the most
primitive encryptions like ROT 13 and so. For anything more-or-less
serious there is not any bijection in either way.

Lasse Rieichstein Nielsen has already explained how an encryption
function and its inverse are bijective on the domain of the encryption
function and its image. A bijection exists whenever there's a
one-to-one correspondence between two sets; here those sets are
plaintext and ciphertext. I didn't think that was a terribly difficult
concept, but apparently...

 

[Michael Wojcik]

A cryptographic hash function is an encryption algorithm, whether you like
it or not.

No, it is not, and your insistence otherwise does not make it so.

In any event, there are other irreversible verifiers which are not
encryption functions even under half-assed folk definitions of the
term. Cryptographic hashes are often used as verifiers because they
have various desirable properties (they're fast, finding a preimage is
expensive, etc), but those are extraneous to the actual definition of
a verifier. You could use a CRC as a verifier, for example; it would
have very little strength, because it's easy to find a preimage for
any given CRC polynomial, but it's still a verifier, and it still
can't be reversed to determine the original secret.

"password.length == C" is an irreversible verifier. Trivial to find a
preimage, but it's still a verifier, and still irreversible. Are you
going to claim the length property is an encryption algorithm?

More useful non-encryption verifiers are things like zero-knowledge
proofs, most of which are not even vaguely related to encryption.