I can't seem to find any answers to some questions I have regarding
hash functions and streaming. If anyone can answer those questions, I'd
be extremely grateful.
I have the following scenario:
I have a continuous audio stream of data blocks passing from a server
to a client.
Each block is unencrypted but contains a message digest (hash) of that
block using SHA-1. The message digest is encrypted using RSA with a
private key, creating a digital signature.
At the client side, the public key is used to decrypt the message
digest.
The data block is hashed to produce another message digest.
The two digests are compared to see if they match.
If they do, the data block is accepted. If they do not the data block
is rejected.
I have just heard (although apparently it's old news) that the SHA-1
algorithm
has been fundamentally broken. It doesn't take 2**80 hashes for a
collision to occur, but only 2**69 hashes.
I don't really understand what problem is caused by someone finding a
collision.
So, my questions are:
1. Does this mean that they have reversed the hash back to plaintext?
2. Or have they found some plaintext that hashes to the same value as
some other plaintext? And if so, why is this considered dangerous?
3. How would someone launch an attack against a stream with an
encrypted SHA-1 message digest?
4. If the SHA-1 message digest was not encrypted, what is the worst
that someone could do if they could create a collision?
5. If the stream is very long and the compromised block is just 60
seconds or less of that stream, could a hash collision of that one
block provide a vulnerability for the rest of the stream? Even though
each block will have a completely different hash?
In article <1130183109.913479.124080@g14g2000cwa.googlegroups .com>,
frank <francis.moore@gmail.com> wrote:
:I have just heard (although apparently it's old news) that the SHA-1
:algorithm
:has been fundamentally broken. It doesn't take 2**80 hashes for a
:collision to occur, but only 2**69 hashes.
:I don't really understand what problem is caused by someone finding a
:collision.
:So, my questions are:
:1. Does this mean that they have reversed the hash back to plaintext?
No.
:2. Or have they found some plaintext that hashes to the same value as
:some other plaintext? And if so, why is this considered dangerous?
Yes.
This is dangerous because the new plaintext might say "This is an
billed media stream; automatically pay $25,000 into the following
bank account..."
:4. If the SHA-1 message digest was not encrypted, what is the worst
:that someone could do if they could create a collision?
See above. Or worse.
:5. If the stream is very long and the compromised block is just 60
:seconds or less of that stream, could a hash collision of that one
:block provide a vulnerability for the rest of the stream? Even though
:each block will have a completely different hash?
Yes. Typically in streaming media, blocks identify themselves as
to their type. The injected block doesn't have to identify itself
as pure media data: it could identify itself as some other
block type that the player happens to have a buffer overflow
vulnerability for.
--
I am spammed, therefore I am.
> Hi,
>
> I can't seem to find any answers to some questions I have regarding
> hash functions and streaming. If anyone can answer those questions, I'd
> be extremely grateful.
>
> I have the following scenario:
>
> I have a continuous audio stream of data blocks passing from a server
> to a client.
> Each block is unencrypted but contains a message digest (hash) of that
> block using SHA-1. The message digest is encrypted using RSA with a
> private key, creating a digital signature.
>
> At the client side, the public key is used to decrypt the message
> digest.
> The data block is hashed to produce another message digest.
> The two digests are compared to see if they match.
> If they do, the data block is accepted. If they do not the data block
> is rejected.
You have two layers of cryptography, hash and encryption. In your case the
break of SHA-1 shouldn't be relevant.
Lassi Hippeläinen wrote:
>
> You have two layers of cryptography, hash and encryption. In your case the
> break of SHA-1 shouldn't be relevant.
>
> Eric Rescorla wrote some thoughts about what is secure and what is not in
> his blog (scroll down to Aug 19):
> http://www.rtfm.com/movabletype/archives/2004_08.html
>
> -- Lassi
frank <francis.moore@gmail.com> wrote:
> I have just heard (although apparently it's old news) that the SHA-1
> algorithm
> has been fundamentally broken.
Yes. You could use RIPEMD-160 instead, or use a well known block cipher
in CBC mode and use the last block of it as a hash.
> I don't really understand what problem is caused by someone finding a
> collision.
Trying to be short:
The security of hash functions consists of preventing attackers from being
able to provoke collisions.
If attackers can do this, then there is no security left at all with a hash
function.
Yours,
VB.
--
"Ich bin ein freier Mensch und werde jetzt von meinen Freiheitsrechten
Gebrauch machen - und zwar ausgiebig - natürlich nur in dem Rahmen, den
Otto Schily mir noch zur Verfügung stellt."
Wolfgang Clement am 10.10.05 als Noch-Superminister
Lassi Hippeläinen <lahippel.at.ieee.org@moon.invalid> wrote:
> > I have the following scenario:
> > I have a continuous audio stream of data blocks passing from a server
> > to a client.
> > Each block is unencrypted but contains a message digest (hash) of that
> > block using SHA-1. The message digest is encrypted using RSA with a
> > private key, creating a digital signature.
> > At the client side, the public key is used to decrypt the message
> > digest.
> > The data block is hashed to produce another message digest.
> > The two digests are compared to see if they match.
> > If they do, the data block is accepted. If they do not the data block
> > is rejected.
> You have two layers of cryptography, hash and encryption. In your case the
> break of SHA-1 shouldn't be relevant.
This is wrong.
Yours,
VB.
--
"Ich bin ein freier Mensch und werde jetzt von meinen Freiheitsrechten
Gebrauch machen - und zwar ausgiebig - natürlich nur in dem Rahmen, den
Otto Schily mir noch zur Verfügung stellt."
Wolfgang Clement am 10.10.05 als Noch-Superminister
> Lassi Hippeläinen <lahippel.at.ieee.org@moon.invalid> wrote:
>> > I have the following scenario:
>> > I have a continuous audio stream of data blocks passing from a server
>> > to a client.
>> > Each block is unencrypted but contains a message digest (hash) of that
>> > block using SHA-1. The message digest is encrypted using RSA with a
>> > private key, creating a digital signature.
>> > At the client side, the public key is used to decrypt the message
>> > digest.
>> > The data block is hashed to produce another message digest.
>> > The two digests are compared to see if they match.
>> > If they do, the data block is accepted. If they do not the data block
>> > is rejected.
>> You have two layers of cryptography, hash and encryption. In your case
>> the break of SHA-1 shouldn't be relevant.
>
> This is wrong.
Hmmm... a small brainfart there. The conclusion is correct, but the argument
isn't. The attacks against SHA-1 use chosen plaintext. This case is only
known plaintext, so the attack doesn't work.
Lassi Hippeläinen <lahippel.at.ieee.org@moon.invalid> wrote:
> >> > The data block is hashed to produce another message digest.
> >> > The two digests are compared to see if they match.
> >> > If they do, the data block is accepted. If they do not the data block
> >> > is rejected.
> >> You have two layers of cryptography, hash and encryption. In your case
> >> the break of SHA-1 shouldn't be relevant.
> > This is wrong.
> Hmmm... a small brainfart there. The conclusion is correct, but the argument
> isn't. The attacks against SHA-1 use chosen plaintext. This case is only
> known plaintext, so the attack doesn't work.
If an algorithm is broken, then it's futile to further discuss how to use
it securely.
Yours,
VB.
--
"Ich bin ein freier Mensch und werde jetzt von meinen Freiheitsrechten
Gebrauch machen - und zwar ausgiebig - natürlich nur in dem Rahmen, den
Otto Schily mir noch zur Verfügung stellt."
Wolfgang Clement am 10.10.05 als Noch-Superminister
>If an algorithm is broken, then it's futile to further discuss how to use
>it securely.
Nonsense. The SHA1 attack takes about 2^69 hash operations (not
instructions, but complete hashes). It reduces the effective key
strength by 11 bits. The second article does say that a -single-
collision could likely be found in about 56 hours... at a cost of
$US25M - $US38M.
This isn't the territory of "The VP is a mole for a rival corporation",
this is just the territory of normal risk assessment. *NO* mathematical
crypto function is permanently secure (short of one time pads) if enough
resources are brought to bear on it. Each person must evaluate for
their situation as to whether the information they have is valuable
enough that someone is likely to bother investing tens of millions of
dollars to be able to fake one packet in a datastream that probably
has anti-replay turned on.
The danger to SHA-1 is effectively irrelevant to telecommunications
for all but governments, military, and very large corporations. The
danger to SHA-1 is in digital signature applications: if you can
intercept a digitally signed payout of (say) $100M and use a hash collision
to alter the destination bank encoding, then -that- becomes worth doing.
You have locks on your doors, right? Why do you bother when standard
locks are "broken" by easy techniques such as liquid helium, or new
advances in acids or explosives that would make short work of them?
Why haven't you installed Fort Knox- type security to protect the
contents of your refrigerator? It is because of cost/ benefit/ risk
trade-offs, right? And just so, SHA-1 still has a lot of life in
areas that do not -need- the highest level of security available.
--
If you lie to the compiler, it will get its revenge. -- Eric Sosman
>Lassi Hippeläinen <lahippel.at.ieee.org@moon.invalid> wrote:
>> >> > The data block is hashed to produce another message digest.
>> >> > The two digests are compared to see if they match.
>> >> > If they do, the data block is accepted. If they do not the data block
>> >> > is rejected.
>> >> You have two layers of cryptography, hash and encryption. In your case
>> >> the break of SHA-1 shouldn't be relevant.
>> > This is wrong.
>> Hmmm... a small brainfart there. The conclusion is correct, but the argument
>> isn't. The attacks against SHA-1 use chosen plaintext. This case is only
>> known plaintext, so the attack doesn't work.
>If an algorithm is broken, then it's futile to further discuss how to use
>it securely.
That is of course non-sense. "broken" is not a monolithic property. All
hashes are broken in one way or another, and one can still talk about using
them safely and using them in situations where the way in which they are
broken does not matter (eg all hashes are broken WRT exhaustive search, but
are still used in situations (almost all) in which exhaustive search is too
expensive to carry out. Of course if you have the choice between two
algorithms, one with a known easy break the other without, all other things
being equal you should choose the second.
on 11/2/2005 7:26 AM Volker Birk said the following:
> Lassi Hippeläinen <lahippel.at.ieee.org@moon.invalid> wrote:
>
>>>>>The data block is hashed to produce another message digest.
>>>>>The two digests are compared to see if they match.
>>>>>If they do, the data block is accepted. If they do not the data block
>>>>>is rejected.
>>>>
>>>>You have two layers of cryptography, hash and encryption. In your case
>>>>the break of SHA-1 shouldn't be relevant.
>>>
>>>This is wrong.
>>
>>Hmmm... a small brainfart there. The conclusion is correct, but the argument
>>isn't. The attacks against SHA-1 use chosen plaintext. This case is only
>>known plaintext, so the attack doesn't work.
>
>
> Please read:
>
> http://www.schneier.com/blog/archive...a1_broken.html
> http://www.schneier.com/blog/archive...nalysis_o.html
>
> If an algorithm is broken, then it's futile to further discuss how to use
> it securely.
>
> Yours,
> VB.
The cryptanalysis article does not actually support your conclusion.
Though an attack has been found, it is not a genaral cause for alarm.
The author says:
"For the average Internet user, this news is not a cause for panic. No
one is going to be breaking digital signatures or reading encrypted
messages anytime soon. The electronic world is no less secure after
these announcements than it was before."
Should improvements and better hash functions be sought? Of course. The
author continues to say:
"But there's an old saying inside the NSA: "Attacks always get better;
they never get worse." Just as this week's attack builds on other papers
describing attacks against simplified versions of SHA-1, SHA-0, MD4, and
MD5, other researchers will build on this result. The attack against
SHA-1 will continue to improve, as others read about it and develop
faster tricks, optimizations, etc. And Moore's Law will continue to
march forward, making even the existing attack faster and more affordable."
My conclusion? SHA-1 is not "broken", but it is not perfect either. No
shock there. The function is useful as long as a normal risk analysis
is done. To paraphrase (and alter) VB's comment: It *is* useful to
further discuss how to use it (SHA-1) securely.
Walter Roberson <roberson@ibd.nrc-cnrc.gc.ca> wrote:
> Nonsense. The SHA1 attack takes about 2^69 hash operations (not
> instructions, but complete hashes). It reduces the effective key
> strength by 11 bits. The second article does say that a -single-
> collision could likely be found in about 56 hours... at a cost of
> $US25M - $US38M.
> This isn't the territory of "The VP is a mole for a rival corporation",
> this is just the territory of normal risk assessment.
Well, you're forgetting Moore's law and further crypto analysis.
Beside that, _WHY_ the hell should one use cracked algorithms, if
there are some left which aren't?
> *NO* mathematical
> crypto function is permanently secure (short of one time pads)
This is unclear up to now. But: well, and if so? This does not lead to
the conclusion to use cracked algorithms, too.
> You have locks on your doors, right? Why do you bother when standard
> locks are "broken" by easy techniques such as liquid helium, or new
> advances in acids or explosives that would make short work of them?
> Why haven't you installed Fort Knox- type security to protect the
> contents of your refrigerator? It is because of cost/ benefit/ risk
> trade-offs, right? And just so, SHA-1 still has a lot of life in
> areas that do not -need- the highest level of security available.
See <43228b5a@news.uni-ulm.de>
Yours,
VB.
--
"Ich bin ein freier Mensch und werde jetzt von meinen Freiheitsrechten
Gebrauch machen - und zwar ausgiebig - natürlich nur in dem Rahmen, den
Otto Schily mir noch zur Verfügung stellt."
Wolfgang Clement am 10.10.05 als Noch-Superminister
Unruh <unruh-spam@physics.ubc.ca> wrote:
> >If an algorithm is broken, then it's futile to further discuss how to use
> >it securely.
> That is of course non-sense. "broken" is not a monolithic property. All
> hashes are broken in one way or another
Please explain, how to break RIPEMD-160.
Yours,
VB.
--
"Ich bin ein freier Mensch und werde jetzt von meinen Freiheitsrechten
Gebrauch machen - und zwar ausgiebig - natürlich nur in dem Rahmen, den
Otto Schily mir noch zur Verfügung stellt."
Wolfgang Clement am 10.10.05 als Noch-Superminister
John Hyde <EJhyd@netscape.net> wrote:
> The cryptanalysis article does not actually support your conclusion.
> Though an attack has been found, it is not a genaral cause for alarm.
> The author says:
| SHA-1 has been broken. Not a reduced-round version. Not a simplified
| version. The real thing.
<URL:http://www.schneier.com/blog/archives/2005/02/sha1_broken.html>
Everybody is reading what she/he wants to read, it seems.
> My conclusion? SHA-1 is not "broken", but it is not perfect either. No
> shock there. The function is useful as long as a normal risk analysis
> is done. To paraphrase (and alter) VB's comment: It *is* useful to
> further discuss how to use it (SHA-1) securely.
To ask again. _WHY_ should one use a broken algorithm, if there are
algos left, which are not broken, like RIPEMD-160?
Yours,
VB.
--
"Ich bin ein freier Mensch und werde jetzt von meinen Freiheitsrechten
Gebrauch machen - und zwar ausgiebig - natürlich nur in dem Rahmen, den
Otto Schily mir noch zur Verfügung stellt."
Wolfgang Clement am 10.10.05 als Noch-Superminister
:To ask again. _WHY_ should one use a broken algorithm, if there are
:algos left, which are not broken, like RIPEMD-160?
The firewall we use does not support RIPEMD-160, and replacing the
firewalls organization-wide with ones that do, is financially out
of the question unless the risk is quite substantial.
Is the risk quite substantial? The maximum security of data we handle
is "Protected/B", and we only get that high in a few email messages
in which contract terms are discussed. The companies we are dealing
with think nothing of sending those email messages in plain text over
the Internet, so our protection is *much* stronger than theirs.
Other than that... well we get the occasional press release that we are
supposed to hold for a couple of days until official release, but it's
information that would have been released anyhow, and chances are that
strong hints about it have been "strategically leaked" to the press
so they can write an article about it to appear on the same day we make
the official announcement.
If someone really wants to spend $US30M and several days of computation
to be able to fake a single data packet ... well, they would still need to
know the proper nounce for the instant (anti-replay) in order to be able to
inject the packet successfully, and the TCP sequence number of the
stream they wanted to inject into... If they put $US30M into the effort,
they might be able to confuse an internal WINS server about which
internal host was which... for about 1 1/2 minutes until the real host
rebroadcast. Confusing the internal WINS server to point to an outside
host probably wouldn't get very far as we block outgoing traffic
of the sort that would want WINS tracking anyhow...
Our entire yearly budget is only about $US5M; if someone was really
willing to spend $US30M to inject a single packet, then I'm sure
they could find *much* more cost-effective ways to achive whatever
effect they wanted. Is our risk meaningfully increased because now
someone could bribe one of our users for $50,000 (out of $US30M) instead
of bribing one of our users for $50,000 (out of $US1B) ?
--
All is vanity. -- Ecclesiastes
Walter Roberson <roberson@ibd.nrc-cnrc.gc.ca> wrote:
> Volker Birk <bumens@dingens.org> wrote:
> ><URL:http://www.schneier.com/blog/archives/2005/02/sha1_broken.html>
> :To ask again. _WHY_ should one use a broken algorithm, if there are
> :algos left, which are not broken, like RIPEMD-160?
> The firewall we use does not support RIPEMD-160, and replacing the
> firewalls organization-wide with ones that do, is financially out
> of the question unless the risk is quite substantial.
My condolences. ;-) But I think, Cisco will move soon, too. And: as an
alternative to hashing algorithms, you could use block ciphers, too.
Of course, usually this is somewhat slower. But it's secure, if the
block cipher is secure (and the implementation, of course).
> Is the risk quite substantial?
I don't think, that it would be a good idea to even discuss broken
algorithms. We can discuss, of course, what could be a way to substitute
by-and-by.
If an algorithm is broken once, then usually the risk is very high
that someone finds a way to complete this work nearby by developing a
working attack.
SHA-1 is broken now. We all don't know a working attack on implementations
of it now for many cases. As yet. But this possibly is only a question of a
short period of time from now on.
Yours,
VB.
--
"Ich bin ein freier Mensch und werde jetzt von meinen Freiheitsrechten
Gebrauch machen - und zwar ausgiebig - natürlich nur in dem Rahmen, den
Otto Schily mir noch zur Verfügung stellt."
Wolfgang Clement am 10.10.05 als Noch-Superminister
Walter Roberson wrote:
> Other than that... well we get the occasional press release that we are
> supposed to hold for a couple of days until official release, but it's
> information that would have been released anyhow, and chances are that
> strong hints about it have been "strategically leaked" to the press
> so they can write an article about it to appear on the same day we make
> the official announcement.
Rather timely, given today's news from Estonia...
Alun.
~~~~
[Please don't email posters, if a Usenet response is appropriate.]
--
Texas Imperial Software | Find us at http://www.wftpd.com or email
23921 57th Ave SE | alun@wftpd.com.
Washington WA 98072-8661 | WFTPD, WFTPD Pro are Windows FTP servers.
Fax/Voice +1(425)807-1787 | Try our NEW client software, WFTPD Explorer.
Hash functions and streaming 
Linear Mode
