Prev: Call for participants
Next: My Cryptography that is Currently on the Table.
From: TC on 9 Jul 2010 08:07
On Jul 9, 8:38 pm, Kristian Gjøsteen <kristiag+n...(a)math.ntnu.no>
wrote:
> TC  <gg.20.keen4s...(a)spamgourmet.com> wrote:
> >So the problem is not the lack of a public key scheme - it's
> >the lack of a known shared secret - right?
>
> Well, if you have a shared secret, what do you need the passphrase for?
>
> --
> kg

I don't understand.

I'm surmising that the reason I can't do what I want, is:

* BECAUSE I don't have shared secret.

* NOT because of Francois' reason, namely, that I do not have a
public key scheme.

??

Cheers,
TC
From: Francois Grieu on 9 Jul 2010 08:42
On 09/07/2010 11:28, TC wrote:
> I'm really surprised to see that there is apparently no way to do what
> I want. It seems like such a simple requirement from an end-user
> viewpoint!
>
> To restate the requirement: the user enters a passphrase. The
> ciphertext does not decrypt to the original plaintext. I want to
> unambigously detect whether that was because (1) the user entered the
> wrong passphrase, or (2) the ciphertext has been altered (for any
> reason - including by a malicious attacker).
>
> Francois Grieu says: "There is no meaningful way to distinguish "wrong
> password" from "malicious alteration" without a public key scheme."
>
> I'm no expert, but on reflection, it seems to me that the problem is
> this.
>
> There's /no shared secret/ in this system. The only secret is the
> passphrase. But if someone enters the passphrase wrongly, then, they
> no longer share a secret with the person who encrypted the data. And
> "no shared secret" means, "no way to distinguish 'wrong passphrase'
> from 'malicious alteration'" - right?
>
> If the users /did/ have a shared secret, /seperate to/ the password,
> then I could achieve what I want - /without/ using a public key
> scheme. So the problem is not the lack of a public key scheme - it's
> the lack of a known shared secret - right?

Indeed, if a shared secret unknown and unusable by the attacker
is assumed, one can distinguish a malicious alteration from a
wrong password.

I was previously assuming that the password which wrong entry must
be detected encompasses any shared secret. It makes sense since
if you have a shared secret, it is tempting to derive the encryption
key from that secret, and then you do not need a password, nor a
password check.

Notice that hiding the shared secret to the malicious attacker
(e.g. in a Smart Card) is not enough. If the attacker is able to use
an encryption device containing that shared secret, she can encrypt
any message using any password, and maliciously substitute that with
a genuine cryptogram; this malicious alteration will be diagnosed as
a wrong password on the receiving side.

Francois Grieu
From: Ilmari Karonen on 20 Jul 2010 09:37
On 2010-07-09, TC <gg.20.keen4some(a)spamgourmet.com> wrote:
>
> I'm really surprised to see that there is apparently no way to do what
> I want. It seems like such a simple requirement from an end-user
> viewpoint!
>
> To restate the requirement: the user enters a passphrase. The
> ciphertext does not decrypt to the original plaintext. I want to
> unambigously detect whether that was because (1) the user entered the
> wrong passphrase, or (2) the ciphertext has been altered (for any
> reason - including by a malicious attacker).

Some general comments on this thread here:

Assuming that:

1. the only inputs to the decryption/verification function are the
ciphertext C and the passphrase P,
2. the passphrase P contains no checksum or other means by which its
validity might be verified independently of C,
3. the ciphertext C might have been modified in an arbitrary manner
by an adversary, and
4. the adversary, knowing P, is able to generate valid ciphertexts,

then Kristian is right: there is no fully reliable way to distinguish
malicious changes in C from accidental changes in P. The proof is
simple: the adversary might've replaced C with an alternative, but
valid, ciphertext C' generated using an arbitrary passphrase P'.
Without additional inputs, there is no way then for the verifier to
know that the real passphrase is P and not P'.

That said, some partial solutions might still be possible. In
general, there are (at least) two ways to approach the problem:

a) validate the passphrase independently of the ciphertext, and
assume the ciphertext has been modified if the passphrase looks
valid but verification fails, or

b) include more than one element in the ciphertext that can be
independently used to validate the passphrase, and assume the
ciphertext has been modified if only some but not all of them
pass.

If you get to generate the passphrases, approach A is easy: just
include a simple checksum in the passphrase to catch accidental
errors. Alternatively, you might simply ask the user to enter the
passphrase twice, and warn them if the passphrases don't match. Of
course, neither of these solutions helps if the user enters the wrong
passphrase correctly, e.g. if the passphrase has changed but they're
still trying to use the old one.

Also, if you could store even a few bits out of the adversary's reach,
you could calculate a truncated (iterated) hash of the passphrase and
store it there. Even an 8-bit hash would give less than a 0.5% chance
of a wrong passphrase being accepted.

Approach B seems doomed to fail due to the proof above; an adversary
can always replace the ciphertext with a valid one created using a
different passphrase. However, why would an adversary deliberately
construct a ciphertext using the wrong passphrase? One should perhaps
not _entirely_ rule out the possibility of an adversary who just wants
to mess with the user's head, but in general, assuming that the
adversary wants their ciphertext to have a chance of being accepted, I
see only the following possibilities:

a) The adversary knows the correct passphrase, or has fully broken
the MAC so that they can construct valid ciphertexts without
knowing the passphrase. In this case, we're screwed anyway, so we
might as well ignore this scenario.

b) The adversary doesn't know the passphrase, but is trying to guess
it. If the passphrase is picked from a sufficiently large pool,
such an "on-line" brute force attack is impractical, particularly
if the attacker only gets a limited number of attempts. Indeed,
if they have access to the original ciphertext, they'd be better
off running an off-line brute force attack against it.

c) The adversary doesn't know the passphrase, but has partially
broken the MAC so that they can construct valid ciphertexts with
some non-negligible probability p < 1.

This last case is one which we might, in fact, hope to detect (with
probability 1-p). Indeed, there are many ways to do so, several of
which have already been mentioned.

For example, we might pick a random salt and prepend that, plus a hash
of the passphrase + salt, to the ciphertext. (We could even use a
truncated hash here too, if we're willing to accept some smallish
probability of a mistyped passphrase being mistaken for tampering.)
An attacker presumably wouldn't want to change them, since that would
just increase the chance of the ciphertext being rejected; but if they
match the passphrase even though the MAC for the actual message fails,
we know that something bad is going on.

Of course, we might imagine a probabilistic attack on the MAC that
would _also_ allow the construction of new salt/hash pairs matching
the passphrase _if and only if_ the MAC spoofing was also successful.
It's hard to quantify the likelihood of this (though it seems low),
but using sufficiently different primitives for the salt and the MAC
intuitively ought to reduce the odds of such a serendipitous attack.

(Note that this is essentially the same solution as the "store a
checksum out of the adversary's reach" approach above. It's just that
we're relying on the adversary, under some assumptions, not _wanting_
to change the checksum, rather than on them not being able to.)

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
First  |  Prev  | 
Pages: 1 2 3 4
Prev: Call for participants
Next: My Cryptography that is Currently on the Table.