Schneier on Security

Time for NIST to have another competition?

So what hash functions are available that don't have a substantially similar construction? AFAIK, RIPEMD160 and the SHA256-384-512 series are of the same sort, and the attack could in principle work for them as well. There's Tiger, which appears quite different, and Whirlpool. Any other suggestions?

This is, it would appear, a collision attack, not a preimage attack, so I guess we have some time to phase out the old hash functions.

Feb. 7, 2005 Hashing out encryption:

http://www.fcw.com/fcw/articles/2005/0207/web-hash-02-07-05.asp

Federal agencies have been put on notice that National Institute of Standards and Technology officials plan to phase out a widely used cryptographic hash function known as SHA-1 in favor of larger and stronger hash functions such as SHA-256 and SHA-512.

2**69 operations is still an awful lot of operations. What is it that lets us say that 2**69 is "broken" but 2**80 is "not broken"?

> (although it doesn't affect applications such as HMAC)

Bruce,

Pardon my ignorance but can you elaborate why this doesn't affect HMAC?

That's 2**11 less operations. Let's say breaking this (2**69 ops) takes the NSA a week. If it had been 2**80, it would have taken 2048 weeks, or 39 years. If it would have taken the NSA (or whomever) a year to break SHA-1 before, it could be broken in 4 hours.

My guess would be it would still take a lot longer than a week - but would now be in the realm of possibility, whereas before it would have been in the lifetime(s) range. However, this is totally a wild-assed-guess, based on the assumption that it was expected to take 100+ years before this to crack.

"...whereas before it would have been in the lifetime(s) range."

Either way, it's well within the statute of limitations for whatever crime you've committed. ;-)

He said 69!!!!!!!!

COOOOOOOOLLLLLL!!!!!!!!!!!!!!

I don't think any public calculation has successfully solved a problem which required as much as 2^69 work. It will be interesting to see if this motivates people to search for an actual SHA-1 collision. Exhibiting a collision always has more impact than a theoretical break.

Of course, these researchers have yet to publish their techniques. Isn't it kind of contradictory to the spirit of academic research to keep your methodology secret for so long? It's been six months now since their MD5 results.

Regarding how long it should take to break... Let's assume that a single CPU can tackle 2**32 ops/sec. (About 4 billion, so assuming each op is one cycle, about 4 GHz... Gross oversimplification, but it makes the math pretty easy.) So, how long would it take to do 2**69 ops?

2**37 seconds of CPU time. About 4000 years.

So, if you have a 4000 node cluster, it ought to take about a year, which would be well within the statute of limitations, for most crimes and jurisdictions... :)

Brute forcing, using the same hypothetical cluster, would have taken over 2000 years. So, I guess today's lesson is that it isn't completely broken, but it certainly ain't secure.

2^69 is still a lot of work, with current processors and electricity prices. But with Moore's progression and the lessons of history, people who were planning on 2^80 complexity for a bit of futureproofing will be very unhappy with 2^69.

I'm not clear on why anyone would've been using 80 bits in the first place. A 20% reduction in 80 bits is a big deal, but a 20% reduction in 256 bits is still way outside what we'd consider practical in the forseeable future. Bits are cheap, use lots!

With the maxim about attacks getting better I'd be worried that with the rate that the SHA family attacks have improved in the last few months we could see even more serious breaks within a year or two.  Not long ago we had reason for deep concern, now we've got reason for outright worry.

Jordan is correct - 2^69 is still a large data space to search.
However, as Randell points out, this is a lot better than 2^80.
Assume you had 100,000 CPUs each capable of 4,000,000,000 tests per second.
That works out to 1,475,739 seconds to find a collision or about 17 days.
It is unlikely that such equipment exists, but it gives an idea of a possible worst case.
However, many digital signatures need to be secure much longer than 3 weeks.
Think of a contract for a 30-year mortgage.
The previous brute force mechanism (2^80) might have been secure for up to 95 years and reasonable.

How effective is this attack? For example can it change "attack at dawn" to "attack at dusk" in a file that
has been compressed and then had a sha-1 md made?
Because at the end of the day isn't that the point of MDs?

-A curious cryptographer...

It is not 2^11 fewer operations. It is 2^11 _times_ fewer operations, roughy 1/2050th the work.

The point isn't so much that it takes less time but that it has an large and now known weakness. It is very likely other weaknesses will come to light making it useless for secure hashing.

@Bruce
I don't know if you saw the Cryptographer's Panel today, but Avi Shamir mentioned the Chinese team's report and the need for better hashing.

oh my. its amazing how human brainpower [and some patience and creativity] can ultimately defeat ANYTHING presented to it.

Good for the chinese team! [congratulations!]

time to build something better than SHA1

I think it is important to note that (from what I've heard, I haven't seen the paper either...) this collision attack is not very "real world" useful. Their attack is focused on taking a certain number of operations to come up with two hunks of data that result in the same hash.

In my opinion, a "real world" attack would be one which given a blob which has already been hashed, would come up with another blob which results in the same hash. To my knowledge, nobody has any useful attacks in that direction yet, although some would argue based upon this research that it may just be a matter of time.

Then we of course need to get into whether that is really useful either. If I find out that "I agree to purchase 100 units for $500" and "*(\D$Hw&72d98a %93di(hd eLKH%ap$#" results in the same hash, how helpful is that to me? How is a lawyer is going to prove to a jury that I may have actually signed the garbage instead of the purchase agreement? So, there is even more work to be done to make it a useful real world attack, wherein you might take the original signed text (modified for your evil purposes), append a null character, and then add garbage until the hashes are equal--and hope the UI was poorly written and just displays up to the first null.

If this solution lends itself to distributed computation, and one in a million people online were to participate in such a project, the first publicly generated SHA-1 collision should be produced by the end of 2010.

That is assuming the use of cheap modern desktops, Moore's law, and linear growth of online population in line with the predictions of Computer Industry Almanac (140 million new users/year, and thus net growth of 140 new participants/year -- probably under-estimating growth of participation here).

If participation were higher, say one in a thousand, we'd be cracking them at a rate of one every other month.

Peter, let me guess.. you're from slashdot?

Would a combination of multiple hash algorithms make it more difficult to obtain collissions?

say MD5 + SHA?

> 2**69 operations is still an awful lot of
> operations. What is it that lets us say that
> 2**69 is "broken" but 2**80 is "not broken"?
The 2**80 is a brute-force attack. Less than brute force means that it is "broken", for the reason cjr gave. ("broken" and defeatable in practice are two different things). The only exception to this convention I'm aware of is in public-key cryptography.
AFAIK, all known public-key algorithms are vulnerable to less than brute-force attack. The key sizes are boosted to compensate, for lack of any alternative.

Where people take p = password

p' = sha1(p)
or
p' = sha1(p, nonce)

This case is reasonably safe as you're allowed collisions in the problem space (different users can (and probably do) choose the same password)... as long as p' is not exposed to the attacker.

The problem sets in when you use MD5 or SHA1 for digital signatures:

For example:

md5sum file

This allows an attacker *theoretically* to change file and compute the same hash from a different bag of bytes. This eliminates the trust you might have had in the file being made available to you.

One ISP I know "verified" downloads from a nearby mirror using a similar method. It wasn't until I pointed out that an attacker could change the source by contributing to the application. Verification of checksums / hashes is not the be all and end all, but this break by the researchers makes it more difficult to trust the class of hashes which have been shown to be weak for verification purposes.

Andrew

Very impressive if it pans out. In some ways, the writing was on the wall with their earlier work, but you still just someone don't beleive it's coming. WOW!

Looking forward to a public release after they get any typos out (understandable).

The design structure of all hash functions in the MDx and SHA family is based on an unbalanced Feistel network structure opearting in a non-linear feedback shift register mode which we told last year june in our new hash function design paper called CRUSH mentioning that this structure is a single point of failure for cryptography.

Regards
Praveen Gauravaram

SHA-1 is broken but not yet cracked. This is a compressor function collision, getting to a full hash function collision has not yet happened.

We have a couple of years (but not much more) to plan a transition to more secure algorithms.

Okay, could someone a bit more well-versed in the Hows and Whys of cryptography step up and explain why a hash algorithm that is "broken", when used in an HMAC setup, is suddenly "not broken"?

Is it simply because we're suddenly involving a secret key?

If so, could not these advances mean that obtaining that secret key may be a bit easier than we previously thought, too?

I notice everyone are still using Moore's law in their calculations, didn't they notice things are changing, we're hitting the limit.

http://www.gotw.ca/publications/concurrency-ddj.htm

Digital signatures aside, I think this attack would be devestating to the current wave of file-sharing networks. The one I am most familiar with is the ed2k network, especially using the eMule client. eMule has since distanced itself from the original MD4 (yes, you read it right) used for integrity checking in favor of SHA-1. However, if even this has been cracked, there's now nothing stopping an attacker from substituting random garbage for blocks of legitimate content...and without anyone being the wiser until it's too late. The blocks would continue to pass virally from node to node with no way to determine whether they're legit or not. Score +1 for the **AA's of the world =(

if SHA-1 is broken now,
what are the alternatives now?
Any suggestions?

Louis Cordier:
It is true that ordinary processors dont double their raw processing speed every 18 months anymore.
However, the trend goes now to multi-core processors. A multi-core processor is perfect for cracking SHA-1 since there are a lot of independent calculations to do.

I agree with my collegues above: 2^69 is still huge.

And what I might like to add is that we are talking about _speculation_ as long as the paper is not published. Until we don't see the paper (with all the qualifications that must be fulfilled for the attack to work), I think it is quite dangerous to discuss sheer assumptions. (although I am very exited to get my hands on this paper and nervous about the possible consequences)

@Mike
> However, if even this has been
> cracked, there's now nothing stopping
> an attacker from substituting random
> garbage for blocks of legitimate
> content
It isn't _that_ broken. Computing power is still stopping the attackers.

And also in your scenario. If I were the attacker, I would simply tell you that my random bytes had the legitimate SHA1-value. You still wouldn't find out I fooled you until the whole file was downloaded.

SHA1 in p2p-networks serves as a way for users to compare two files. You still have to trust the one giving you the SHA1-value. Integrety of the file is not assured.

If the argument that it was attacked by 2^69 computations is true (we don't have proof yet) then we can safely say it is broken as it is less than B'day on SHA-1. It is the time for us to look at new designs. The good start is to have a new kind of iterative structure first than Merkle-Damgard structure. So the question is what kind of abstract structure or a hash function model can resist these attacks. Once the compression function is attacked, the attack can be extended to other blocks as well with further research. So hash value and the chaning value should be different and chaning value should be more than the hash value. Interesting to see Stefan Lucks proposed structure.
The future research should proceed on these lines. We need to have secure hash functions and give importance to efficiency once you achieve security in the first instance. Anyway, the performance expected from a hash function depends on the application

Andrew Wade wrote:
> The 2**80 is a brute-force attack. Less than

> brute force means that it is "broken", for the

> reason cjr gave. ("broken" and defeatable in

> practice are two different things). The only

> exception to this convention I'm aware of is in

> public-key cryptography.

> AFAIK, all known public-key algorithms are

> vulnerable to less than brute-force attack. The

> key sizes are boosted to compensate, for lack

> of any alternative.

All hashes are necessarily vulnerable to less than brute-force attack as well, simply because they are hashes. Anytime hashtext is allowed to be shorter than the corresponding plaintext, collisions must occur because the possible combinations are more finite. There is no way around this, so like for public-key cryptography, one must compensate by having longer hashtext. The perceived usefulness of modern hashes appears to exceed the perceived usefulness of the 8-bit checksum by a magnitude proportional to how many more collisions the 8-bit checksum would have in the given application. Defining "broken" as "requiring less than brute force" therefore renders the term "broken" meaningless since, in the absence of more "secure" hashing algorithms, making the hashtext longer necessarily reduces collisions. However, because when the length of the hashtext reaches the length of the plaintext, you essentially have symmetric cryptography with a known key and algorithm (unless of course the algorithm allows collisions when hashtext length equals plaintext length, currently seen as undesirable), there is a paradox where a longer hashtext is also less secure. The true usefulness of a hash is proportional to how much processing it takes to find a collision. If we assume that the more processing it takes to calculate a hash in the first place, the more processing it would take to find a collision, the challenge becomes the development of hash algorithms that take more processing power. If available processing power were to cease increasing, the practicality of finding collisions would also cease to increase, and there would be no further need or use for newer hash algorithms that take more processing power. As long as that doesn't happen, expect each hash algorithm to be replaced periodically with a newer one that takes more steps to calculate. After all is said and done, that is really the only way to stay ahead of the game.

what now? With MD5 and SHA-1 being cracked, what hash function is considered secure?

I have a number of hash functions here in source code format:

http://www.maradns.org/download/sums-20011111.tar.bz2

And papers for these hash functions:

http://www.maradns.org/download/sums-papers-20010818.tar.bz2

Some interesting stuff is here:

Tiger: 192-bit hash. Not broken yet.

Whirlpool: 512-bit hash; uses a Rijndael (AES) variant as the compression function.

AEShash: Hash algorithm that uses Rijndael as the compression function.

- Sam

Maybe we should start encoding meta-data along with the hash, so instead of trusting only on the hash to confirm that the message is from who sign it, we would encode along the message, the size, type and whatever characteristic could define the message.

For instance, suppose I sign the message "Hi, I'm Victor", along with the hash it would contain the size (14 bytes), type (English text), encoding (7bits ASCII) and how about the range of codes used in the messages (from U+0027 - U+0074).

A good hash would give a uniformly distributed random hash for the message, so it is safe to assume that even if we could find a collision, it would be highly unprovable that it would satisfy all the meta-data. In some cases it could be provable that this kind of hash is unbreakable, since there is a finite number of messages that satisfy the meta-data (if you could hash all possibilities and verify that there were no collisions you're 100% safe).

History shows that reducing the brute-force key space of an algorithm is only the beginning of the end: I am sure that the attack will be optimized and improved, so that the key space will be further reduced. This has been shown during several attacks on FEAL, too.

That means that we should not trust that in near future the key space stays at 2**69. When similar hash algorithms also shows the SHA-1 weakness, then we need an new hash algorithm nearly immediatly.

I'm not a cryptographer but to those who want to know why HMAC use of a hash function is not broken, it's because, as somebody else suggested, of the key.

With a digital signature all you have to do is find another blob of data which hashes to the same hash. You are free to choose any blob of data.

With HMAC you are not free to choose any other blob of data because a secret key is always added to the data before it is hashed and you don't know that secret key. So you still need to guess the key or the person verifying the HMAC will get a different hash than you.

(On a side-note, how the heck do I get line breaks when I post comments?)

Oh, they show up in the real post but not in the preview. Marvelous.

Pardon my ignorance, but what good does it do me if I can find a few collisions with a digital signature on a document? Aren't the collisions going to be a bunch of gibberish that hashes to the same value? How would I use the gibberish to cause trouble? I can see a DOS scenario, where I replace a good message with gibberish, but I can't see how I could massage a message to say something intelligible but different, like "deposit this in another account," or "I inhaled," or whatever.

The importance is that often there is someplace in the document that you can change willy-nilly, while retaining semantic meaning.

for CRC-32, all you needed was 4 bytes in a row, and you could completely control the hash of the document. I don't know how many are needed for SHA, but let's say that it is on the order of 80 bytes:

- In a jpeg, you could add a comment
- In a MS .doc, you could add meta-data
- in an exe, you might be able to add stuff at the end, outside the instruction stream.
- In HTML, add stuff in a javascript comment or after the closing html tag

For anything but raw text, it really isn't that hard to find a large number of contiguous bytes you can modify without changing the semantic meaning.

Scott, you ignore the fact that forcing a collision can be done not only with a gibberish message but also with a message containing a few bytes of gibberish. Consider the case where a cryptosignature is used to keep a machine from running untrusted software. An executable file can contain a few bytes of gibberish without compromising its ability to run (just stick it in an unused constant somewhere), and then be signed as if it came from a trusted source. This is a bad thing indeed.

A few people here are questioning the meaningfulness of this attack, because they think that a collision to a known plaintext "I'm Bill." would look something like ",#&($@<?}*(&³µG" - which would be basically useless, I would usually think the same.

BUT, remember the MD5 attack... when I first saw it, I was VERY impressed NOT because they DID find a collision, no! But because the collision had only A FEW bytes changed to the original message.

Look here: http://www.x-ways.net/md5collision.html

You can see there are ONLY 24 bits (or even less) changed (which is 2.4% of this 1024bit message).

So this scenario IS a reason to panic. And as soon as they will publish a SHA-1 collision with the same 'features' as the MD5 collision, we are in trouble.

http://eprint.iacr.org/2004/199

Previous attacks by the same team of researchers

hmmm.

SHA-1 has 2**80 unique hash-numbers. fine.
But isnt the odd to get one 1/2**79, because statistically, I hit one after 2**79 tries after trying all?

please excuse my bad english.

--
grisu

Concatenating MD5 and SHA1 doesn't give you as much extra security as you'd think, because of this beautiful result from Joux at last year's Crypto. Basically, if it takes you 2^{69} work to cause a collision in SHA1 in a general context (from most any starting hash value), the most it can take to find a collision for SHA1 || MD5 is about 2^{75}--you find 64 places in the message where you can insert a colliding value for SHA1, and then do a 2^{64} search to find a collision between those in MD5. (If this isn't clear, go read the Crypto 2004 paper--the result is not hard to understand at all!)

HMAC is harder to attack because the attacker doesn't know the internal values of the hash function when she's choosing her message blocks. To the extent that she needs to know what some bits of the hash chaining value are to choose the next message bit, her attack is blocked. But since Wang & company ahven't published details of their attacks, it's really not possible to know how big a problem this is.

The eprint archive has a nice paper by Phil Hawkes and Greg Rose trying to reconstruct the Wang attack on MD5, which is probably getting a lot of downloads right now....

--John Kelsey

Please explain me one thing.
Everyone keep saying: SHA-1 is broken... It takes 2^69 operation to broke it...

I dont understand.
Every hashing algorithm will have collisions. Every. Because we have limited hash space to represent unlimited variants of data. Yes? Yes.
So EVERY algorithm can be broken. They manage to collide in 2^69 tries of 2^80 possibilites. ENORMOUS LUCK. Its not something to remember.
Lets say, after introduction od SHA-256 I broke it in 20 tries. Luck. Then you say SHA-256 is broken??? How could you use word broken... I merly manage to collide.
So concluding. Using your words, every hashing function is broken. Only time and luck is important.
I think that it doesnt matter if someone find colision or not. It wont change nothing. Keys must became longer, as computing power grows greater, to keep teoretical computing time relatively impassible long. And of that time is 2^99999 years, and someone manage to find collision id 5 days? It changes nothing. He got lucky.

Just to clarify, SHA-1 produce a hash of 160 bits (20 bytes). Collisions can be found with 2**(bits/2) by the brithday attack - go look at google for hash and birthday attack for explanation.

160 bit hash => 2**80 steps to find a collision.

SHA-256 has a 256 bit hash (32 bytes) and works with a similar algorithm to SHA-1. So 2**128 steps is brute force. Using that (or SHA-512) would give a period of grace, but the attack may well be applicable to these, so a hash with a completely new basis would be "a good thing" (tm).

With the rider that anything new probably needs several years of cryptanalysis before we would trust it ...

rainbow hash tables anyone?

Bruce,

You didn't actually read the paper, did you? If you did, you would have noticed the footnote which says that the attack isn't on "the real thing".

Stop spreading rumors.

I like the way your titillating announcement of the work of Wang, et al upholds predictions you made late last year, Bruce. How lucky for you!

For reference: http://www.computerworld.com/securitytopics/security/story/0,,95343,00.html

Btw, how obnoxious is it to reference something that no one else can read?

Hey - other anon person, you're anon - why don't you post a link to your resource???

*disgusted*

After last summer's announcement of the initial hash research, I wrote what many have said is a good overview of the subject:
An Illustrated Guide to Cryptographic Hashes
http://www.unixwiz.net/techtips/iguide-crypto-hashes.html

Having actually implemented both SHA-1 and MD5 in assembly (while I was in college, in a calculus class), the length of the actual data is appended to the last null-padded block. So, even small changes in the size have a significant impact on the final sum, and cannot be covered up by any blocks of data coming after it (except for man-in-the-middle, but that is useless in most situations). Other meta-data should be used as a signature, where it is included in the original data, outside the data, where it is hashed, and then both hashes are hashed (basically what PGP does).

In the message "Hi, I'm Victor" there are 12 different characters. If only these 12 characters are allowed, there are 12**14 = 1283918464548864 or 1.28e+15 possibilities that could satisfy all the meta-data. The total possibilities for a SHA-1 sum is 2**160 ~= 1.46e+48. Using 1 bit as a flag for each sum would require 2**160 /8 ~= 1.83e+47 ~= 1.62e+32 PB (1PB= 1024*1TB= 1024*1024*1GB, I think) of storage. In the much reduced 12**14 number of possibilites, this would still require a minimum of 12**14 *20 ~= 2.57e+16 ~= 23,914,845 GB ~= 22.8 PB of storage, if each sum was unique (we cannot use the 1 bit mapping in this reduction).

Using the techniques of this not yet published paper could reduce the storage requirement, but the only messages that could be proved to have a unique hash are those that are shorter in length than the hash. In the case of SHA-1, this is 20 bytes.

Using the vulnerabilities to prove the authenticity of a short message is not yet too practical.

A pretty secure hash method would be something like the following:

fast:
d1= hash1(message);
d2= hash2(message);
d3= hash1((message+d1)+d2);

slow:
d1= hash1(message);
d2= hash2(message);
d3= hash1((d1+message)+d2);

The 2 hash functions MUST be different to a good degree (I believe SHA-1 and MD5 suffice, from my experience). The + operator is equivalent to appending the right operand onto the left, i.e. "a"+"b"="ab". d1, d2, and d3 are the message digests. All three digests MUST be distributed, along with what format the digests are in (hexadecimal or base64), along with what hash functions were used, along with the designation "slow" if the slow method is used ("fast" is default).

The fast method could be computed fairly quickly by doing the 2 hashes on each block (making use of the processor cache), except for the final blocks. The slow method should be more secure, as only d1 and d2 could take advantage of the cache effect (d3 would have to be computed from scratch).

Creating a collision on d1 and d2 would be pretty difficult, d3 would be much more. d1 and d2 MUST be hashes of only the original message, as hash2(mesage+d1) could make it easier to find a collision (as the effective message would then be different).

I am not a cryptographer, but this scheme seems obviuosly much harder to crack for many reasons.

As far as I know, this scheme is original, but is similar to PGP and 3DES. I think this is an obvious possible solution, and as such cannot be patented.

Tell me what you think.

It's important to qualify what is meant by "broken" -- the ability to find collisions weakens the use of a cryptographic hash in digital signatures.

The speedup is about 0.0005 over the brute force average for finding a collision.

Interesting, but not quite as interesting as colluding Poker Bots.

>rainbow hash tables anyone?

>Posted by: hendler at February 16, 2005 10:01 AM

Creating rainbow tables for an algorithm has nothing to do if it is broken or not.

rainbow tables use the hashing algorithm the way it is supposed to be used and creates a "dictionary" of cleartext->hashes value.

You can generate rainbow tables for any algorithm you know the workings of (preferably have source code too). The thing is having enough disk space to store that information..

Try this: Use a rainbow table generator which tells you the etsimated key space and disk space, enter the following parameters.
Charset: full
Hash: SHA1 Min Len: 1 Max Len: 263
Chain count: 57,000,000 No of Tables:
9,999,999,999 (maximum)

With this data, the program i am using says the key space is 1.#INF, disk space: 1.665.497.180.-45 GB, and success probability: -1.#INDO (-1.#J%)
Obviously, this is too large for the program to even calculate the key space.

And that's for the domain, if you want to calculate the range try:
Sha1, min 1, max 160, charset hex, chain count 40000000, no of tables 9999999999.
The RANGE key space is merely 4.867*10^192.

I hope you get the message.. If you want to do rainbow tables, better have a lot of disks.. But since NIST couldn't do it to validate the algorithm, then neither can you.

How is the 2^69 hash operations assertion to be understood? Is the cost the same no matter what the message input size? Also, can collisions be found for any input message?

Re compute power:

The IBM/SONY/Toshiba Cell processor has 1 ppc64 core and 8 special processors (SPE's) per 30-watt chip, clocked at 4.5 GHz. Each SPE can dispatch two instructions per clock; each SPE has 128 registers that are 128-bits wide and are joined with 4 128-bit busses running at half clock speed. This provides something on the order of 100+ (and maybe more) general purpose Giga integer ops for things like code-breaking.

Conclusion: 1000 Sony playstation-3's appropriately hacked would draw 30KW of power (a bit on the high-end for a suburban home, but achievable) and could achieve 2^36 ops/sec x 2^16 secs/day x 2^10 consoles == 2^62 ops/day -- OK, but each round might take 2^8 (?) ops so its maybe 2^54 rounds/day within reach of a crazy retired .com CEO, from their garage. That's an awesome large number...

If you're using a supercomputer that does 40 teraflops (40 trillion operations per second), then it would take... *thinks*... between 12 and 13 years, and about 6 years on average.

It's not inconsistent with the tennents of research to not be publicly trumpeting this research.

First of all, I presume that the current distribution is for the purposes of refereeing for a peer-reviewed publication. They may also be asking for verification of their results -- given that it could be extremely embarassing to have this wrong (in proportion to the notoriety gained by having this right.

This is also somewhat sensitive information, so they may want 'white hats' to have a couple of weeks knowledge to prepare for the stuff that hits the fan when this becomes public knowledge.

One way of looking at it is that breaking SHA-1 with 2**69 operations is still more work than brute forcing MD5 with 2**64 operations.

I wrote the "MD5 To Be Considered Harmful Someday" paper that discussed attacks given only Wang's test vectors. This is...a bit different.

It's a 2^69 attack against SHA-1, which has the distinct problem of being 32x the complexity of bruting MD5 (2^5 = 32). We never did see a MD5 brute; we needed Wang's reduction to a 2^24 to 2^32 for us to eventually end up with vectors.

I don't expect to ever see SHA-1 collision vectors. We still need to migrate away, but this is akin to Dobbertin's proof of possibility right now. Respond, don't panic.

Don't tell me not to panic! I will panic immediately, THANK YOU!

What's the practical implication of this research?

For example, how hard is it to create an X.509 certificate that looks like a valid Microsoft code-signing certificate with the attacker's public key? I'm assuming it is relatively trivial for the attacker to create a certificate extension containing the appropriate random garbage, but is it really 2^69 operations to select the right garbage?

theory-edge,
mailing list/discussion for cutting edge developments in mathematics & algorithmics, click my initials

MY PERSONAL TOP SECRET TO BREAK CODES: ParaModulation SATisfiability (Para-SAT) and Quantum Computing (Schor-like).

Dictionary Attacks ARE INSUFFICIENT!!!.

948fad80398ce3df645c91da456c2669e7fed61f
crack this hash :)

>And that's for the domain, if you want to calculate the range try:
>Sha1, min 1, max 160, charset hex, chain count 40000000, no of tables 9999999999.
correction on my previous post:
min here should be 160 as the key length is fixed. Sorry about that.

Actually, this sort of attack has real uses, assuming you have the computing power to do it, which organizations that can produce fast hardware implementations on custom chips can.

If you can produce two SHA1 strings that collide and are a multiple of the fundamental hash length, any two strings that begin with those two will also collide.

This means that I can trivially produce any number of strings, whose last bits I can choose, and they will collide.

Consider a message format where the first two bytes are the length of the first object and then after that object are other objects. I can pick any chunks that collide, pad out to object length, and then follow with objects of my choosing. The two final strings will collide in their hashes, be different, and have a lot of content over which I have control.

You can do the same thing for the end of a message.

grisu: No, it's 2^40 operations. Google for 'birthday paradox'.

DS

Yeah... so... why isn't the paper generally available yet? Is it unfinished (and thus premature)? Or do the authors just have a penchant for childishness? Perhaps they'd rather sell it copy-by-copy for a low low price of only 500 RMB! Act now!

All I'm seeing so far is "Bruce Sez he saw something that could have meant that maybe SHA-1 is broken."

Which is great and all, but since there are so many crypto people in the hizzy (and would-be crypto people, too), why doesn't someone work out how reasonable it is to take this purely based on trust and reputation. And what impact it has on someone's reputation to say something was broken without being able to point to proof.

Is peer review a dead art? Replaced by cult of personality?

I really wish people would stop saying "broken". Yes, I know that cryptographically it is broken. But practically, at least for now, SHA-1 is still plenty strong. 2^69 attempts is a whole lot harder than finding a non-crypto flaw in a system. As Schneier himself admitted in his most recent book, crypto isn't the weak link in most systems. Focusing on a (significant) weakness in a crypto algorithm gives the impression that the crypto is what makes the system secure, when in fact even a flawed algorithm like SHA-1 is still the strongest link in the security chain.

Even when these same people "broke" MD5, it was still a pretty limited break for most practical purposes. They could, maybe, generate two messages with the same hash, but that was far and away different from being able to generate messages that collide with a given hash.

> Is peer review a dead art? Replaced by cult of personality?

Yes to both. And Bruce is up there at the front of the seething masses.

Just Re: SHA-1/MD5 and all the "hash-bash": I think it's important to emphasize that we are NOT talking about finding a collision to an arbitrary (i.e. chosen) plaintext message. Just colliding two random ones, at better than Bday paradox. So we're not all doomed just yet, contrary to the girl who stood outside Moscone today with the sign (see http://hisown.com/temp/02160020.JPG and ...21.JPG ;-)

J

> Is peer review a dead art? Replaced by cult of personality?

>> Yes to both. And Bruce is up there at the front of the seething masses.

I posted the *disgusted* comment yesterday - and am so happy to see that I'm not the only one NOT sitting on the "Bruce Sez" bandwagon...

Double-nots aside, it's a good day!

When this team broke MD5, they published two strings which had the same MD5 hash. It's trivial to verify - once you've got your head around the byte-ordering issues :-)

So for me the question is: has this team actually created two distinct strings which hash to the same SHA-1 value?

If they have, why not just post them so we can all verify it? But if not, then I don't think it's reasonable for anyone to claim point-blank that SHA-1 has been "broken". "Weakened", maybe.

Based on Bruce's reputation, I'd say they've probably done it - but it would be helpful if he could clarify this by saying outright that the paper does (or does not) include an actual SHA-1 collision.

Even though an attacker can replace a document with digital signature with a garbage document with the same hash, it should be easy to convince any judge or jury that if someone can produce a readable document with the same hash, it is likely that such a document is original. The question in my mind is how many tries would it take to create a document that is at least 50% similar to the original document and produces the same hash.

I guess the lesson with digital signature is that any digital signature scheme should allow multiple hashes to be used! It's probably very very difficult to find 2 messages that produce identical MD5 *and* SHA-1 hash values. Is it?

Cryptography has a long history of people saying, "don't worry, it's just a scratch."
This announcement means that it is time to look very seriously at the entire SHA-x family, and its alternatives. It is almost guaranteed that any weakness will be a foundation for more powerful attacks in the future. Expect (2 ^ 69) to have a considerably smaller exponent within 12 months.

Exciting news!

For people who have doubts about the news, please read this:

Chinese researchers compromise SHA-1 hashing algorithm

http://www.commsdesign.com/news/showArticle.jhtml?articleID=60401254

>>>>>>>>>>>>>>>>>>>>>>>>>

......

Shamir and others said they believe the work of the Chinese trio will probably be proven to be correct based on their academic reputations, although details of the paper are still under review.

......

"This break of SHA-1 is stunning," said Ronald Rivest, a professor at MIT who co-developed the RSA algorithm with Shamir. "Digital signatures have become less secure. This is another reminder that conservatism is needed in the choice of an algorithm," added Rivest at the panel session.

Rivest noted that one member of the China team, Lisa Yin, was a PHD student who studied under him at MIT. Another member of the team was responsible for cracking the earlier MD5 hashing algorithm.

"I have strong reasons to believe the results [of the paper] are correct," Rivest said.

......

Another article at http://www.theregister.co.uk/2005/02/17/sha1_hashing_broken/ says that it is official that SHA-1 was broken ...

If it is based on the same source here, the conclusion may be pre-mature, but it does contain something extra ...

"A collision has been discovered in the full version in 269 hash operations, making it just possible to mount a successful brute-force attack with the most powerful machines available today."

"A collision has been discovered" ?!!! Can anyone confirm that? I sure can wait for 2**xxx days :)

What I've seen is a 58/80 step collision which is said to have taken 2^{33} hashing operations. This is up on the web at http://makeashorterlink.com/?D1605138A

They don't have the ability to do 2^{69} operations (that's a lot of work!). But since the previous best attack was estimated at 2^{71} work to break 53/80 steps, this is a pretty nice demonstration.

--John

HERE's the paper
http://theory.csail.mit.edu/~yiqun/shanote.pdf

transend the divine water
red ocean ninja clan

Wowie! Thanks, transend!!! ^_^

just fyi, I found the summary paper on Lisa's web site

http://theory.csail.mit.edu/~yiqun/shanote.pdf

The paper on MD5 collision by Wang last year
http://eprint.iacr.org/2004/199.pdf

>>>
Please explain me one thing.
Everyone keep saying: SHA-1 is broken... It takes 2^69 operation to broke it...

I dont understand.
Every hashing algorithm will have collisions. Every. Because we have limited hash space to represent unlimited variants of data. Yes? Yes.
So EVERY algorithm can be broken. They manage to collide in 2^69 tries of 2^80 possibilites. ENORMOUS LUCK. Its not something to remember.
Lets say, after introduction od SHA-256 I broke it in 20 tries. Luck. Then you say SHA-256 is broken??? How could you use word broken... I merly manage to collide.
So concluding. Using your words, every hashing function is broken. Only time and luck is important.
I think that it doesnt matter if someone find colision or not. It wont change nothing. Keys must became longer, as computing power grows greater, to keep teoretical computing time relatively impassible long. And of that time is 2^99999 years, and someone manage to find collision in 5 days? It changes nothing. He got lucky.
<<<

But with a collision in hand, it becomes easier to find more collisions.

That, and anyone so astronomically lucky isn't going to a computer scientist, they're going to be living off the lottery.

Great academic exercise. In the real world though, attackers are going to look for much easier ways to break in than using brute force against a hash. Why bother digging a tunnel into someone's house if he leaves a window open? Those storing and transmitting classified or very sensitive info should be using a cryptologic system anyway and not just a SHA-1 or MD5 hash.

Scott, you ignore the fact that forcing a collision can be done not only with a gibberish message but also with a message containing a few bytes of gibberish. Consider the case where a cryptosignature is used to keep a machine from running untrusted software. An executable file can contain a few bytes of gibberish without compromising its ability to run (just stick it in an unused constant somewhere), and then be signed as if it came from a trusted source. This is a bad thing indeed.

---------------
http://www.ptdd.com
http://www.yiwodisk.com

hi,how are you!

Adeodatus, you are right.

Best solution for the time being is to migrate to higher range.

It doesn't make sense to migrating to 256bit, from the existing 160 bit and wait till 256bit get cracked (by assuming that today's technology won't grow rapidly, which is a big joke).

I feel better to adopt higher than 256 (something like 512), the probability of cracking hash (in what ever way) will reduce at least 1%

"It doesn't make sense to migrating to 256bit, from the existing 160 bit and wait till 256bit get cracked (by assuming that today's technology won't grow rapidly, which is a big joke)."
Unless I'm missing something (and it's not the birthday paradox), 128 bit hashes aren't brute-forceable with today's technology.
The fastest supercomputers in the world are about 2^48 times faster than the electromechanical Mark-I, arguably the first functional computer.
A 256 bit hash takes 2^64 times as long to brute force as a 128 bit hash, if you have unlimited memory.
In short, 256 bits is plenty.

I love chickens

www.video-poker.tvheaven.com

F5fPxdTq8eJeuqSVejGmq2bp0hU1rv9UelE23rOyfSJQWPR94NpiPSRjVpWraaNby5wlkxMIu4csKR0=

crack this :)

Thanks transend for the link to the paper

http://www.cgisecurity.com

After another posting on /. about PGP shifting to a stronger algorithm and reading some of the thread's comments I was wondering...

One Way Hash functions takes a large set of data
(source) and produce a relatively short string. Since there is no way (very limited chance) of producing the original source data from the hash. All attacks are basically equivalent to "buffer overflow" attacks. Where the attacker modifies the source to produce an equivalent hash. Since we believe the hash is authentic to start with, why not add a source-size parameter to the hash. Most of these attacks modify and append data to the source data to make the hashes match. Given the additional (trusted) information about the
source's size it would basically limit the usefulness of this type of attack. This will then
basically be a protocol/conformity constraint on the modified source data which would make things
a bit more difficult for any attacker. Other parameters could also be employed, for example a source-symbol frequency, etc.

Q. What do you get when you break a cryptographic hashing algorithm?

A. A new compression algorithm.

www.beyond-science.com broke every laws of physics

also look at http://www.texas-holdem-playing-cards.com/

> Unless I'm missing something (and it's not the birthday paradox), 128 bit hashes aren't brute-forceable with today's technology.
I was missing something, and 128 bit hashes are brute-forceable. See the newer thread for a low-memory technique:
http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html

I still think 256 bit hashes have a comfortable margin.

How is the 2^69 hash operations assertion to be understood? Is the cost the same no matter what the message input size? Also, can collisions be found for any input message?

Someone has done a great thorough job. And the confidence is not so profound any more.

The IBM/SONY/Toshiba Cell processor has 1 ppc64 core and 8 special processors (SPE's) per 30-watt chip, clocked at 4.5 GHz. Each SPE can dispatch two instructions per clock; each SPE has 128 registers that are 128-bits wide and are joined with 4 128-bit busses running at half clock speed. This provides something on the order of 100+ (and maybe more) general purpose Giga integer ops for things like code-breaking.

all block ciphers are breaked bye "hashim search algorthim" see {cryptology group}
in yahoo

new formula of number factorization
p^2+q^2-w^2=j
where
p*q=j p,q prime numbers
also
p/q+q/p- c=1 where c=w^2/j
is enouph to break
RSA IN POLYNOMIAL TIME

"new formula of number factorization
p^2+q^2-w^2=j
where
p*q=j p,q prime numbers
also
p/q+q/p- c=1 where c=w^2/j
is enouph to break
RSA IN POLYNOMIAL TIME"

I get this sort of nonsense in e-mail all the time. This is the first one you all get to see.

Since the invention of the RSA public-key algorithm, all cryptographers get this sort of nonsense all the time. We either have to read through them all, which is a waste of time, or ignore them all, which has the potential of ignoring an actual breakthrough.

This is why RSA Security invented the RSA Factoring Challenge. Basically, these are a series of increasingly long numbers to factor. Some of them have been factored already, but many have not.

http://www.rsasecurity.com/rsalabs/node.asp?id=2092

Now, every time I get one of these "I can factor numbers faster than everyone else," I send them to the webpage. If they can factor numbers that no one else can, they'll have no problem getting every mathematician to listen to them. If they can't, mathematicians will have no problem ignoring them.

"all block ciphers are breaked bye "hashim search algorthim" see {cryptology group}
in yahoo"

This kind of thing we don't even bother responding to.

I'm not an expert, so please don't make fun of me if I sound like a complete idiot.

I can see that this crack poses a theoretical threat to the security of SHA1, but how does it affect a regular user? What good would it do an adversary to find a collision in someone's digital signature? The adversary could change the original message to the collision he/she had found, but odds are that the "collision message" would make absolutely no sense whatsoever. The recipient would get a string of absolute jibberish that was certified as being sent by his/her friend. I'm probably overlooking something here, but what security risk does this really cause? There would be a real danger if someone found a way to reverse the hash and reveal the plaintext message that the sender had signed.

My apologies if I sound like a fool.

Yeap

Tell me if I am wrong but if digital signatures can be forged due to SHA1 collisions, it will be probably much more interesting and easier to create fake certificates than fake messages.

A fake certificate can be reused much more times than a fake message and the 'return on investment' will be higher for anybody wanting to steal identity...

http:// bdsm-comics-1001.tripod.com/3d_spanking_comics.html 3d spanking comicshttp:// bdsm-comics-1001.tripod.com/3d_britney_spears_hardcore_comics.html 3d britney spears hardcore comicshttp:// bdsm-comics-1001.tripod.com/3d_sadistic_comics.html 3d sadistic comicshttp:// bdsm-comics-1001.tripod.com/3d_free_full_length_hentai_movies.html 3d free full length hentai movieshttp:// bdsm-comics-1001.tripod.com/3d_hines_torture_drawings.html 3d hines torture drawingshttp:// bdsm-comics-1001.tripod.com/3d_free_zoo_comics.html 3d free zoo comicshttp:// bdsm-comics-1001.tripod.com/3d_bdsm_cartoons.html 3d bdsm cartoonshttp:// bdsm-comics-1001.tripod.com/3d_gary_roberts_art.html 3d gary roberts arthttp:// bdsm-comics-1001.tripod.com/3d_comic_hardcore_bondage.html 3d comic hardcore bondagehttp:// bdsm-comics-1001.tripod.com/3d_torture_comic.html 3d torture comichttp:// bdsm-comics-1001.tripod.com/3d_raunchy_comics.html 3d raunchy comicshttp:// bdsm-comics-1001.tripod.com/3d_sexy_comics.html 3d sexy comicshttp:// bdsm-comics-1001.tripod.com/3d_comics_hardcore.html 3d comics hardcorehttp:// bdsm-comics-1001.tripod.com/3d_sick_cartoon_porn.html 3d sick cartoon pornhttp:// bdsm-comics-1001.tripod.com/3d_violent_comix_britney.html 3d violent comix britneyhttp:// bdsm-comics-1001.tripod.com/3d_joseph_farrel.html 3d joseph farrelhttp:// bdsm-comics-1001.tripod.com/3d_girls_raped_by_animals.html 3d girls raped by animalshttp:// bdsm-comics-1001.tripod.com/3d_bdsm_rape.html 3d bdsm rapehttp:// bdsm-comics-1001.tripod.com/3d_zoo_toons.html 3d zoo toonshttp:// bdsm-comics-1001.tripod.com/3d_cruel_rape_drawing.html 3d cruel rape drawinghttp:// bdsm-comics-1001.tripod.com/3d_free_incest_porn_comics.html 3d free incest porn comicshttp:// bdsm-comics-1001.tripod.com/3d_cartoon_rape_comic.html 3d cartoon rape comichttp:// bdsm-comics-1001.tripod.com/3d_free_bondage_cartoons.html 3d free bondage cartoonshttp:// bdsm-comics-1001.tripod.com/3d_extreme_drawings.html 3d extreme drawingshttp:// bdsm-comics-1001.tripod.com/3d_adult_comic_book.html 3d adult comic bookhttp:// bdsm-comics-1001.tripod.com/3d_cartoon_torture.html 3d cartoon torturehttp:// bdsm-comics-1001.tripod.com/3d_free_comix_bdsm_porn_xxx.html 3d free comix bdsm porn xxxhttp:// bdsm-comics-1001.tripod.com/3d_bestiality_hentai.html 3d bestiality hentaihttp:// bdsm-comics-1001.tripod.com/3d_dirty_art_drawing.html 3d dirty art drawinghttp:// bdsm-comics-1001.tripod.com/3d_hardcore_porn_comics.html 3d hardcore porn comicshttp:// bdsm-comics-1001.tripod.com/3d_raunchy_porn.html 3d raunchy pornhttp:// bdsm-comics-1001.tripod.com/ 3d bdsmhttp:// bdsm-comics-1001.tripod.com/3d_bdsm_art.html 3d bdsm arthttp:// bdsm-comics-1001.tripod.com/3d_incest_comics_free.html 3d incest comics freehttp:// bdsm-comics-1001.tripod.com/3d_erotic_comix.html 3d erotic comixhttp:// bdsm-comics-1001.tripod.com/3d_torture_cartoon.html 3d torture cartoonhttp:// bdsm-comics-1001.tripod.com/3d_extremecomics.html 3d extremecomicshttp:// bdsm-comics-1001.tripod.com/3d_extreme_porn.html 3d extreme pornhttp:// bdsm-comics-1001.tripod.com/3d_bdsm_comix_free.html 3d bdsm comix freehttp:// bdsm-comics-1001.tripod.com/3d_comics.html 3d comicshttp:// bdsm-comics-1001.tripod.com/3d_britney_spears_abducted_comix.html 3d britney spears abducted comixhttp:// bdsm-comics-1001.tripod.com/3d_comic_rape.html 3d comic rapehttp:// bdsm-comics-1001.tripod.com/3d_comics_bdsm.html 3d comics bdsmhttp:// bdsm-comics-1001.tripod.com/3d_cartoon_porn_comics.html 3d cartoon porn comicshttp:// bdsm-comics-1001.tripod.com/3d_anime_rape_comic.html 3d anime rape comichttp:// bdsm-comics-1001.tripod.com/3d_lesbian_comics.html 3d lesbian comicshttp:// bdsm-comics-1001.tripod.com/3d_related.html 3d relatedhttp:// bdsm-comics-1001.tripod.com/3d_torture_cartoons.html 3d torture cartoonshttp:// bdsm-comics-1001.tripod.com/3d_comic_art_adult.html 3d comic art adulthttp:// bdsm-comics-1001.tripod.com/3d_secret_police_by_gary_roberts.html 3d secret police by gary robertshttp:// bdsm-comics-1001.tripod.com/3d_adult_comics.html 3d adult comicshttp:// bdsm-comics-1001.tripod.com/3d_lust_comic.html 3d lust comichttp:// bdsm-comics-1001.tripod.com/3d_xxx_comic_strip.html 3d xxx comic striphttp:// bdsm-comics-1001.tripod.com/3d_domination_comics.html 3d domination comicshttp:// bdsm-comics-1001.tripod.com/3d_raped_comics.html 3d raped comicshttp:// bdsm-comics-1001.tripod.com/3d_free_extreme_comix.html 3d free extreme comixhttp:// bdsm-comics-1001.tripod.com/3d_torture_toons.html 3d torture toonshttp:// bdsm-comics-1001.tripod.com/3d_free_comix.html 3d free comixhttp:// bdsm-comics-1001.tripod.com/3d_naked_disney.html 3d naked disneyhttp:// bdsm-comics-1001.tripod.com/3d_cruel_bondage_drawings.html 3d cruel bondage drawingshttp:// bdsm-comics-1001.tripod.com/3d_free_toon_rape_comics.html 3d free toon rape comicshttp:// bdsm-comics-1001.tripod.com/3d_comics_xxx.html 3d comics xxxhttp:// bdsm-comics-1001.tripod.com/3d_snuff_sex.html 3d snuff sexhttp:// bdsm-comics-1001.tripod.com/3d_comix_xxx.html 3d comix xxxhttp:// bdsm-comics-1001.tripod.com/3d_comix_adult.html 3d comix adulthttp:// bdsm-comics-1001.tripod.com/3d_comix.html 3d comixhttp:// bdsm-comics-1001.tripod.com/3d_lesbian_series.html 3d lesbian serieshttp:// bdsm-comics-1001.tripod.com/3d_brutal_rape_in_comics.html 3d brutal rape in comicshttp:// bdsm-comics-1001.tripod.com/3d_britney_comic_dungeon.html 3d britney comic dungeonhttp:// bdsm-comics-1001.tripod.com/3d_torture_drawing_damian.html 3d torture drawing damianhttp:// bdsm-comics-1001.tripod.com/3d_rape_sadistic_drawings.html 3d rape sadistic drawingshttp:// bdsm-comics-1001.tripod.com/3d_free_beastiality_comics.html 3d free beastiality comicshttp:// bdsm-comics-1001.tripod.com/3d_porn_comics.html 3d porn comicshttp:// bdsm-comics-1001.tripod.com/3d_torture_comix.html 3d torture comixhttp:// bdsm-comics-1001.tripod.com/3d_fuck_toons_bdsm.html 3d fuck toons bdsmhttp:// bdsm-comics-1001.tripod.com/3d_cartoon_bondage.html 3d cartoon bondagehttp:// bdsm-comics-1001.tripod.com/3d_hugemusclecomix.html 3d hugemusclecomixhttp:// bdsm-comics-1001.tripod.com/3d_comics_gothic_rape.html 3d comics gothic rapehttp:// bdsm-comics-1001.tripod.com/3d_sick_comix.html 3d sick comixhttp:// bdsm-comics-1001.tripod.com/3d_snuff_comix.html 3d snuff comixhttp:// bdsm-comics-1001.tripod.com/3d_pistures_of_famous_people_in_2004.html 3d pistures of famous people in 2004http:// bdsm-comics-1001.tripod.com/3d_britney_spears_comix.html 3d britney spears comixhttp:// bdsm-comics-1001.tripod.com/3d_beastiality_drawing.html 3d beastiality drawinghttp:// bdsm-comics-1001.tripod.com/3d_gary_roberts_britney.html 3d gary roberts britneyhttp:// bdsm-comics-1001.tripod.com/3d_zoo_comics.html 3d zoo comicshttp:// bdsm-comics-1001.tripod.com/3d_adult_comic_series.html 3d adult comic serieshttp:// bdsm-comics-1001.tripod.com/3d_beast_hentai.html 3d beast hentaihttp:// bdsm-comics-1001.tripod.com/3d_extreme_drawing.html 3d extreme drawinghttp:// bdsm-comics-1001.tripod.com/3d_sex_comics.html 3d sex comicshttp:// bdsm-comics-1001.tripod.com/3d_comics_dirty.html 3d comics dirtyhttp:// bdsm-comics-1001.tripod.com/3d_sex_comix.html 3d sex comixhttp:// bdsm-comics-1001.tripod.com/3d_drawing_bondage.html 3d drawing bondagehttp:// bdsm-comics-1001.tripod.com/3d_free_adult_comics.html 3d free adult comicshttp:// bdsm-comics-1001.tripod.com/3d_cartoon_rape.html 3d cartoon rapehttp:// bdsm-comics-1001.tripod.com/3d_sex_comics_rape.html 3d sex comics rapehttp:// bdsm-comics-1001.tripod.com/3d_britney_rape_comics.html 3d britney rape comicshttp:// bdsm-comics-1001.tripod.com/3d_rape_cartoons_and_poser.html 3d rape cartoons and poserhttp:// bdsm-comics-1001.tripod.com/3d_hardcore_rape_comics.html 3d hardcore rape comicshttp:// bdsm-comics-1001.tripod.com/3d_cartoon_rape_comics.html 3d cartoon rape comicshttp:// bdsm-comics-1001.tripod.com/3d_sex_drawings.html 3d sex drawingshttp:// bdsm-comics-1001.tripod.com/3d_lesbian_comic.html 3d lesbian comic