Prev: Call for participants
Next: My Cryptography that is Currently on the Table.
From: TC on 5 Jul 2010 02:37
On Jul 5, 10:17 am, mike clark <m...(a)netadv.net> wrote:
> On Jul 4, 2:24 am, TC <gg.20.keen4s...(a)spamgourmet.com> wrote:
> > Hi folks
>
> > Say I encrypt some data with a symmetric stream cipher.
>
> > When the data is DEcrypted, is there any way to know if the right key
> > was used or not, WITHOUT relying on known plaintext?
>
> > Here's what I'm thinking:
>
> >    temp = CIPHER (key, plaintext + HASH (plaintext))
>
> >    ciphertext = temp + MAC (key, temp)
>
> > Then on decryption:
>
> >    1. Check MAC. If wrong, the ciphertext has been altered. Otherwise,
> > the ciphertext is intact: proceed to step 2.
>
> >    2. Decrypt using relevant key.
>
> >    3. Detach and check the hash. If correct, the RIGHT decryption key
> > was used, so the decrypted text should be correct; otherwise, the
> > WRONG decryption key was used, so the decrypted text is useless.
>
> > (1) Is there anything clearly wrong with that scheme?
>
> > (2) Can I use the same key for encrypting and MACing (as shown)?
>
> > (3) Is it ok to HASH the plaintext, or should it be MAC'd?
>
> > Please note, I'm not asking about key strengthening, salting, known
> > plaintext attacks on symmetric stream ciphers, and so on. I'm only
> > interested in whether you can tell if the right decryption key was
> > used, without relying on known plaintext!
>
> > TIA,
> > TC
>
> An authenticated encryption mode such as GCM would work well, as would
> a MAC (as you have already suggested). If you are generally interested
> in the topic of authentication, here are two papers that I have found
> interesting and practical:
>
> The Order of Encryption and Authentication for Protecting
> Communications. (Or: How Secure is SSL?), by Hugo Krawczyk (http://www.iacr.org/archive/crypto2001/21390309.pdf)
>
> Practical Crypto Attacks Against Web Applications, by Thai Doung and
> Juliano Rizzo (https://media.blackhat.com/bh-eu-10/whitepapers/
> Duong_Rizzo/BlackHat-EU-2010-Duong-Rizzo-Padding-Oracle-wp.pdf)
>
> The first paper is especially interesting for your case. Your example
> is correct in doing encrypt then mac. In that paper it discusses
> problems with other orderings. The second paper is a very easy read on
> what happens if you do things very wrongly. Basically it outlines a
> number of attacks where one has used the value of padding for
> authentication instead of a proper MAC.- Hide quoted text -


Thanks to everyone who replied so far.

Mike, I'll read the references you've given me. Unfortunately, I
ballsed-up the question by not articulating an important requirement :-
( And my solution doesn't work at all, as I discovered last night
when I coded it up and gave it a run!

Can I indulge on everyones' patience, and start again with a better
problem description.

I have a few hundred bytes of data to encrypt with a user passphrase.
The user must re-enter the passphrase whenever he wants the data
decrypted. The passphrase is the only secret that enters the system.
The system can not have any other secrets, except for the passphrase,
and things that can be calculated from the passphrase.

I have access to a symmetric stream cipher, a 128 bit cryptographic
hash function, an HMAC function based on that hash, and a source of
random values of any size, eg. to use as salts.

On the face of it, the solution is simple: generate a key by hashing
the passphrase plus a random salt; encrypt the data using that key;
then MAC the result to prevent bit-flipping attacks. Kristian says to
use different keys for encrypting and MACing. So: (using || to mean
concatenation)

key1 = HASH (passphrase || salt1)
key2 = HASH (passphrase || salt2)
temp = salt1 || CIPHER (key1, plaintext)
ciphertext = temp || MAC (key2, temp)
discard salts, keys, temp.

HOWEVER!

The decrypted data is passed to another application. The other
application may be damaged if the decrypted ciphertext doesn't match
the original plaintext. So it's important to actively detect all cases
where that can occur. As far as I can see, there are only two such
cases:

(1) The ciphertext has been altered, or
(2) The user enters the wrong passphrase.

In case (1), I want to say "Parameter file corrupt" (or somesuch), and
refuse to try and decrypt it at all. In case (2), I want to say
"Invalid passphrase", and decline to send the incorrectly decrypted
data to the other application.

The solution I proposed before, had a MAC and a hash. I thought the
MAC would handle (1), and the hash would handle (2). But if the user
enters the wrong passphrase, the MAC fails, so I get "Parameter file
corrupted", instead of "Invalid passphrase".

So, is there any way to distinguish cases (1) and (2), under the
restrictions described?

Hopefully that's a better problem description!

TIA,
TC
From: Kristian Gj�steen on 5 Jul 2010 03:14
TC <gg.20.keen4some(a)spamgourmet.com> wrote:
>I have a few hundred bytes of data to encrypt with a user passphrase.
>The user must re-enter the passphrase whenever he wants the data
>decrypted. The passphrase is the only secret that enters the system.
>The system can not have any other secrets, except for the passphrase,
>and things that can be calculated from the passphrase.
>
>I have access to a symmetric stream cipher, a 128 bit cryptographic
>hash function, an HMAC function based on that hash, and a source of
>random values of any size, eg. to use as salts.
>
>On the face of it, the solution is simple: generate a key by hashing
>the passphrase plus a random salt; encrypt the data using that key;
>then MAC the result to prevent bit-flipping attacks. Kristian says to
>use different keys for encrypting and MACing. So: (using || to mean
>concatenation)
>
> key1 = HASH (passphrase || salt1)
> key2 = HASH (passphrase || salt2)
> temp = salt1 || CIPHER (key1, plaintext)
> ciphertext = temp || MAC (key2, temp)
> discard salts, keys, temp.

Is it correct to discard the salts? If so, how do you recover the keys?

The more conventional way to derive keys is to use something like

master key = PBKDF(passphrase, salt)
key1 = HASH( "1" || master key)
key2 = HASH( "2" || master key)

>The decrypted data is passed to another application. The other
>application may be damaged if the decrypted ciphertext doesn't match
>the original plaintext. So it's important to actively detect all cases
>where that can occur. As far as I can see, there are only two such
>cases:
>
>(1) The ciphertext has been altered, or
>(2) The user enters the wrong passphrase.
>
>In case (1), I want to say "Parameter file corrupt" (or somesuch), and
>refuse to try and decrypt it at all. In case (2), I want to say
>"Invalid passphrase", and decline to send the incorrectly decrypted
>data to the other application.
>
>The solution I proposed before, had a MAC and a hash. I thought the
>MAC would handle (1), and the hash would handle (2). But if the user
>enters the wrong passphrase, the MAC fails, so I get "Parameter file
>corrupted", instead of "Invalid passphrase".
>
>So, is there any way to distinguish cases (1) and (2), under the
>restrictions described?

You could include a MAC of a known plaintext (say "" or "0") with the
ciphertext. If this MAC does verify, but the ciphertext MAC does not,
then someone has tampered with the ciphertext. If the known-plaintext
MAC does not verify, then most likely the user has entered the wrong
passphrase.

Of course, someone who tampers can tamper with the known-plaintext MAC
and make the user believe he is typing the wrong password. I don't know
how to prevent this.

--
kg
From: TC on 5 Jul 2010 04:29
On Jul 5, 4:14 pm, Kristian Gj steen <kristiag+n...(a)math.ntnu.no>
wrote:
> TC  <gg.20.keen4s...(a)spamgourmet.com> wrote:
> >I have a few hundred bytes of data to encrypt with a user passphrase.
> >The user must re-enter the passphrase whenever he wants the data
> >decrypted. The passphrase is the only secret that enters the system.
> >The system can not have any other secrets, except for the passphrase,
> >and things that can be calculated from the passphrase.
>
> >I have access to a symmetric stream cipher, a 128 bit cryptographic
> >hash function, an HMAC function based on that hash, and a source of
> >random values of any size, eg. to use as salts.
>
> >On the face of it, the solution is simple: generate a key by hashing
> >the passphrase plus a random salt; encrypt the data using that key;
> >then MAC the result to prevent bit-flipping attacks. Kristian says to
> >use different keys for encrypting and MACing. So:  (using || to mean
> >concatenation)
>
> >    key1 = HASH (passphrase || salt1)
> >    key2 = HASH (passphrase || salt2)
> >    temp = salt1 || CIPHER (key1, plaintext)
> >    ciphertext = temp || MAC (key2, temp)
> >    discard salts, keys, temp.
>
> Is it correct to discard the salts?  If so, how do you recover the keys?

Sorry, by "discard salts etc.", I meant: to discard the temporary
variables used for the salts and keys. Per my algorithym, the
ciphertext does include salt1, in the clear, at the start. But I
forgot to include salt2, when I modified the algorithm to use a
diferent key for MACing.

I could fix this by including salt2 in the ciphertext, but your next
comment shows I only need one salt:

... The more conventional way to derive keys is to use something like
... master key = PBKDF(passphrase, salt)
... key1 = HASH( "1" || master key)
... key2 = HASH( "2" || master key)

Point taken. That would change my algorithm to:

master key = PBKDF(passphrase, salt)
key1 = HASH( "1" || master key)
key2 = HASH( "2" || master key)

temp = salt || CIPHER (key1, plaintext)
ciphertext = temp || MAC (key2, temp)

retain ciphertext (which contains a copy of the salt, in the
clear,
at the start), but discard everything else, eg. the temp
variable.


>
> >The decrypted data is passed to another application. The other
> >application may be damaged if the decrypted ciphertext doesn't match
> >the original plaintext. So it's important to actively detect all cases
> >where that can occur. As far as I can see, there are only two such
> >cases:
>
> >(1) The ciphertext has been altered, or
> >(2) The user enters the wrong passphrase.
>
> >In case (1), I want to say "Parameter file corrupt" (or somesuch), and
> >refuse to try and decrypt it at all. In case (2), I want to say
> >"Invalid passphrase", and decline to send the incorrectly decrypted
> >data to the other application.
>
> >The solution I proposed before, had a MAC and a hash. I thought the
> >MAC would handle (1), and the hash would handle (2). But if the user
> >enters the wrong passphrase, the MAC fails, so I get "Parameter file
> >corrupted", instead of "Invalid passphrase".
>
> >So, is there any way to distinguish cases (1) and (2), under the
> >restrictions described?
>
> You could include a MAC of a known plaintext (say "" or "0") with the
> ciphertext.  If this MAC does verify, but the ciphertext MAC does not,
> then someone has tampered with the ciphertext.  If the known-plaintext
> MAC does not verify, then most likely the user has entered the wrong
> passphrase.
>
> Of course, someone who tampers can tamper with the known-plaintext MAC
> and make the user believe he is typing the wrong password.  I don't know
> how to prevent this.

But that's the crux of my requirement. To accurately distinguish
between (1) the ciphertext having been altered (accidentally or
maliciously), and (2) the user having entered the wrong password. The
difference is critical from the user's viewpoint. In case (1), he has
to restore the encrypted file from backup - and probably work to find
out how and why it got changed. In case (2), he has to open the safe
to refresh his memory of the proper passphrase.

Is there truly no way to do what I need, with the primitives
available?

If so, is there any way to do it using other/extra primitives?

Thanks again,
TC
From: Kristian Gj�steen on 5 Jul 2010 08:18
TC <gg.20.keen4some(a)spamgourmet.com> wrote:
>But that's the crux of my requirement. To accurately distinguish
>between (1) the ciphertext having been altered (accidentally or
>maliciously), and (2) the user having entered the wrong password. The
>difference is critical from the user's viewpoint. In case (1), he has
>to restore the encrypted file from backup - and probably work to find
>out how and why it got changed. In case (2), he has to open the safe
>to refresh his memory of the proper passphrase.

Perhaps this should be a user interface problem.

>Is there truly no way to do what I need, with the primitives
>available?
>
>If so, is there any way to do it using other/extra primitives?

I can't think of any. It seems impossible.

(Consider the following attack: the user has stored one data file
generated with his passphrase. I substitute my data file generated with a
random passphrase. How is the software to decide whether the user enters
the correct passphrase and the file has been tampered with, or the file
has not been tampered with and the user enters an incorrect passphrase?)

--
kg
From: Francois Grieu on 5 Jul 2010 10:48
On 05/07/2010 14:18, Kristian Gj�steen wrote:
> that's the crux of my requirement. To accurately distinguish
> between
> (1) the ciphertext having been altered (accidentally or
> maliciously), and
> (2) the user having entered the wrong password.

Accidental alteration of the ciphertext can be detected;
just add a field with a big-enough CRC or hash.

Invalid entry of the password for a file that pass the
accidental alteration test can be checked; but for an
off-line verification this weakens security because
it is easier to mount a dictionary attack. The least worst
classical method is to have a field that contains random
"salt" and an appropriate public cryptofunction of salt and
password. It is critical that the evaluation of this function
is SLOW, so as to make password guessing less practical.
For the same reason, there should be a SLOW setup process
for decryption (else redundancy in plaintext may allow a
faster test of the password).

There is no meaningful way to distinguish "wrong password"
from "malicious alteration" without a public key scheme.
However it is possible to ensure that to a receiver with the right
password, a malicious alteration will be detected with the same
level of assurance as that on confidentiality of the plaintext
(that is, an adversary that fails to guess the password despite
existence of a password check field can at worse substitute a
ciphertext for another made by someone with the password;
otheriwise said, the password insures integrity).

One way to do this: cryptogram is
[a] salt (random 256-bit)
[b] ciphertext encrypted with passmord and salt
[c] truncation to 128 bits of
HMAC-SHA256(password, SHA256([a]|[b])|hugestring)
[d] CRC-128(SHA256([a]|[b])|[c])

Receiver recomputes and checks [d], and display "file alterated"
if wrong; then if correct recomputes and checks [c], and display
"wrong password or file alterated" if wrong.

Note: [d] could be CRC-128([a]|[b]|[c]) but it is slightly
slower for big files
Note: some (truncated) hash could be used instead of CRC-128 if
that's convenient.
Note: order of fields proposed allows on-the-fly computation on
both sides (however the receiver must ignore deciphered text if
either check turns out wrong).

Francois Grieu
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Call for participants
Next: My Cryptography that is Currently on the Table.