openssl compatible key and IV calculation

[Rainer Weikusat]

I didn't say 'given the input', I said 'given some properties of the
input'.

Actually 'any properties of the input' and 'any properties of the
output'. And the input itself is surely a property of the input.

Suppose you know (or guess) the input is an English phrase. Does
this make some parts of the output space more likely than others? If it
does you've just weakened your key, by making it less random.

If this was so, someone had inadvertently invented an algorithm
capable of understanding English. This algorithm might be a bad 'key
generation algorithm' but it probably a great, commercial opportunity.

Joking aside, a lossy compression function (like MD5 or any other hash
function) always causes 'loss of information' which implies 'loss of
entropy' if there was more in the input than can remain in the 16
output bytes.

[...]

That and rainbow tables are the only completely-implemented breaks I
know of, yes, but I believe it's considered likely there are ways of
partially predicting the output given limited knowledge of the input
(such as, 'it's probably an English phrase'). I'm not a cryptographer,
and I don't pretend to understand this stuff in detail, but if those who
do are saying 'don't use MD5 for this purpose' ISTM it's a good idea to
listen to them.

Some musings on this:

http://tools.ietf.org/html/rfc6151

 

[Charles DeRykus]

I think you're not entirely understanding where this is used. It's not
used as an ordinary digest function, it's part of the function which
turns a human-readable passphrase into a binary encryption key. It's
obviously necessary that both ends do this the same way, otherwise
typing in the same passphrase won't produce the same key, and the
ciphertext will be undecipherable.

Given that 'openssl enc' has no option to choose the string2key method,
I presume that whatever standard this is implementing (if this isn't
simply an OpenSSL-specific feature) doesn't allow anything except MD5 to
be used. Given that the OP presumably wants the results to be compatible
with OpenSSL, using a string2key function which is more secure but
different from OpenSSL's would be useless.

...that said, I've just looked at the source of 'openssl enc', and there
*is* an apparently-undocumented -md option to choose the hash function
to use for string2key, so it might be possible for the OP to switch to
SHA-1. However, there still isn't an option to add iterations, which is
almost more important. (The documentation for the underlying
EVP_BytesToKey even says that function is deprecated, and apps should
use the PKCS#5 function instead.)

Thanks, I knew minimally that both would need to sync... but little more.

With 1.0.1e, I did spot the -md option in 'man enc' but only the full
option details inside openssl enc:


-md the next argument is the md to use to create a key
from a passphrase. One of md2, md5, sha or sha1


$ openssl enc -a -aes-256-cbc -pass pass:"Secret Passphrase" -base64
-md sha1 -P -S ab001d77079ba218
salt=AB001D77079BA218
key=890B75B7502649E8EF8EAF71B0A978F48229DCC4DE4F43F6825422694B311364
iv =FF77D7B00DD3D950DC7F788E52EC8644

Tweaking sub "aes_key_and_iv" to use Digest::SHA::sha1 does generate an
identical key but, interestingly?, only a partial iv match:

perl tmp.pl "Secret Passphrase" ab001d77079ba218
key [890b75b7502649e8ef8eaf71b0a978f48229dcc4de4f43f6825422694b311364]
iv [ff77d7b00dd3d950ec46c8be1f2ebf5e]

 

[Charles DeRykus]

iteration for SHA-1, or something.

[...]

So... I thought I'd have a look at this, just to see what was going on,
and after spending some time deciphering the apparently-intentionally-
unintelligible OpenSSL code I decided it ought to be doing the same
thing as the Perl. So I tried the Perl with Digest::SHA::sha1, and...
got the same result as with openssl. (Specifically, the same result as
you got with openssl above.)

So either your Digest::SHA is broken (which is possible: there are such
things as compiler bugs, and crypto code is more likely than most to
tickle them) or you changed something else.

Good grief... apologies. It was the latter:


< $d = sha1($d . $pass . $salt);
---

 

[Rainer Weikusat]

Oh, for God's sake... go and read
http://en.wikipedia.org/wiki/Key_stretching

To which part is this supposed to apply? To the fact that
brute-forcing trivial passwords remains trivial no matter how much
time is wasted shuffling the bits contained in them? Or to the other
fact that what is 'a time-consuming calculation' today won't remain 'a
time-calculation' forever and probably not event for long, cf

Some excepts from the Wikipedia article:

The first deliberately slow password-based key derivation
function was called "CRYPT" and was published by Robert Morris
in 1978 for encrypting Unix passwords.

[...]

CRYPT(3) is now considered inadequate. The iteration count,
designed for the PDP-11 era, is too low, 12 bits of salt is an
inconvenience but does not stop precomputed dictionary
attacks,

-------

The commonly accepted Moore's law implies that computer speed
doubles about every 1.5 years. Under this assumption, every
1.5 years one more bit of key strength is plausibly
brute-forcible. This implies that 16 extra bits of strength is
worth about 161.5 = 24 years later cracking, but it also means
that the number of key stretching rounds a system uses should
be doubled about every 1.5 years to maintain the same level of
security.

------

An important consideration to be made is that CPU-bound hash
functions are still vulnerable to hardware
implementations. For example, the literature provides
efficient hardware implementations of SHA-1 in as low as 5000
gates, and able to produce a result in less than 400 clock cycles.

and stop assuming you can solve complicated cryptographic problems
in a few minutes in your head.

There's nothing complicate here. Exactly 262,144 different 'six byte
values' exist. Assuming a key derivation function which takes 1s to
execute, an exhaustive search of this space can be performed in about
3 days by a single computer with a single core CPU. 16 such computers
can do the same in about 4.5 hours. Using a key derivation function
which makes the computer calculating it come to a standstill for 2s
instead increases this to 9 hours. OTOH, using a random 7 byte
password would increase it to about 36 hours for 16 parallell
'crackers'. The obvious conclusion would be that 'obfuscate harder'
is way inferior to 'use higher quality input'.

 

[Rainer Weikusat]

[...]

There's nothing complicate here. Exactly 262,144 different 'six byte
values' exist.

Except not accidentally messing up calculations as it seems . The
number of different 'six byte values' is really 281,474,976,710,656
(256**6) and not 8**6 and an exhaustive search of that with being able
to try one value per second would take a long time. But the basic idea
is nevertheless correct: Increasing the amount of entropy in the input
is vastly more efficient wrt making 'brute-forcing' complicated than
'using a more complicated bit shuffling algorithm'. Doing the example
again for 'three byte values' in order to get reasonably small
numbers:

256**3 is 16,777,216. For a random search, success would 'on average'
require trying half of the possible values. This would be 8,388,608.
At a speed of 1/s, this would take about 97 days. Decreasing the speed
to 0.5/s would mean 'about 194 days'. Using four bytes and the 1/s
scrambling algorithm instead would need about 24,855 days.

 

[Rainer Weikusat]

Ben Morrow <[email protected]> writes:

[MD5 hash]

If this was so, someone had inadvertently invented an algorithm
capable of understanding English. This algorithm might be a bad 'key
generation algorithm' but it probably a great, commercial opportunity.

Joking aside, a lossy compression function (like MD5 or any other hash
function) always causes 'loss of information' which implies 'loss of
entropy' if there was more in the input than can remain in the 16
output bytes.

For 'fairness of discussion': My best attempt to make sense of Ben's
statement is that this refers to what Bob Jenkins (google for 'hash
functions and block ciphers', read the 'Dr Dobbs article) called 'a
funnel in a hash function': One property of a good hash function (in
sense that its output is uniformly distributed) would be
that each output bit depends on all input bits. A hash function is
said to have a funnel when certain input bits or groups of input bits
only affect certain output bits (or groups of output bits). A trivial
example of such a bad hash function would be

sub hash {
my $r;
$r ^= ord($1) while $_[0] =~ /\G(.)/g;
return $r;
}

This takes a string as input and returns 1 byte of output, funnelling
all bits whose offset (counting from the start of the string) is an
integral mutiple of 8 into bit 0 of the output and so forth which
implies that all permutations of some set 'input characters' hash to the
same value. This 'gratuitious loss of information' could be called
'making the input less random'.

But assuming this was meant, that would question the quality of MD5 as
general hash functions, not one of its 'cryptographically interesting
properties'. I admit that I didn't (and won't) try to analyze the MD5
function in this respect but I'm willing to trust the guy who invented
it in this respect unless there's specific information to the
contrary (also, the article I mentioned above uses MD4 as one example
of a hash function and states that it was funnel-free).

Aside: The while-loop above is one way to process some string
character-by-character. Another would be

for (split(//, $string)) {
}

Are there more?

 

[Jim Gibson]

sub hash {
my $r;
$r ^= ord($1) while $_[0] =~ /\G(.)/g;
return $r;
}

Aside: The while-loop above is one way to process some string
character-by-character. Another would be

for (split(//, $string)) {
}

Are there more?

for my $i ( 0..(length($string)-1) ) {
my $c = substr($string,$i,1);
...
}