25:
370:
In some distributed content systems, parties compare cryptographic hashes of files in order to make sure they have the same version. An attacker who could produce two files with the same hash could trick users into believing they had the same version of a file when they in fact did
342:
A hash function has weak collision resistance when, given a hashing function H and an x, no other x' can be found such that H(x)=H(x'). In words, when given an x, it is not possible to find another x' such that the hashing function would create a collision.
235:
in particular both have published techniques more efficient than brute force for finding collisions. However, some hash functions have a proof that finding collisions is at least as difficult as some hard mathematical problem (such as
346:
A hash function has strong collision resistance when, given a hashing function H, no arbitrary x and x' can be found where H(x)=H(x'). In words, no two x's can be found where the hashing function would create a collision.
367:
signature on a hash of the document. If it is possible to produce two documents with the same hash, an attacker could get a party to attest to one, and then claim that the party had attested to the other.
215:
173:
means that any hash function with more inputs than outputs will necessarily have such collisions; the harder they are to find, the more cryptographically secure the hash function is.
227:
are usually designed to be collision resistant. However, many hash functions that were once thought to be collision resistant were later broken.
406:
245:
89:
61:
477:
42:
68:
443:
572:
217:) hash operations on random input is likely to find two matching outputs. If there is an easier method to do this than
75:
108:
187:
577:
57:
411:
401:
46:
130:
137:
is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs
463:
224:
513:
541:
82:
35:
237:
170:
8:
386:
241:
218:
464:"Lecture 21: Collision-Resistant Hash Functions and General Digital Signature Scheme"
360:
484:
522:
433:
391:
177:
447:
396:
381:
509:
440:
566:
437:
180:" places an upper bound on collision resistance: if a hash function produces
122:
526:
364:
24:
507:
232:
221:, it is typically considered a flaw in the hash function.
228:
363:
systems, a party attests to a document by publishing a
355:
Collision resistance is desirable for several reasons.
339:
There are two different types of collision resistance.
334:
269:
is a family of collision-resistant hash functions, if |
191:
265: : {0, 1} → {0, 1}} generated by some algorithm
190:
458:
456:
327:
where negl(·) denotes some negligible function, and
184:
bits of output, an attacker who computes only 2 (or
429:
427:
49:. Unsourced material may be challenged and removed.
466:. Course on Cryptography, Cornell University, 2009
209:
475:
453:
311:, but for any probabilistic polynomial algorithm
564:
424:
450:. Summer course on cryptography, MIT, 1996-2001
307:can be computed within polynomial time given
542:"Lecture 12 of Introduction to Cryptography"
210:{\displaystyle \scriptstyle {\sqrt {2^{N}}}}
478:"How to Break MD5 and Other Hash Functions"
407:Provably secure cryptographic hash function
109:Learn how and when to remove this message
16:Property of cryptographic hash functions
298:compresses the input string, and every
565:
515:Finding Collisions in the Full SHA-1
335:Weak and strong collision resistance
47:adding citations to reliable sources
18:
13:
14:
589:
539:
23:
441:"Lecture Notes on Cryptography"
34:needs additional citations for
533:
501:
469:
412:Error detection and correction
402:NIST hash function competition
244:). Those functions are called
1:
417:
251:
350:
225:Cryptographic hash functions
131:cryptographic hash functions
7:
375:
331:is the security parameter.
10:
594:
573:Symmetric-key cryptography
476:Xiaoyun Wang; Hongbo Yu.
256:A family of functions {
578:Theory of cryptography
211:
58:"Collision resistance"
238:integer factorization
212:
188:
171:pigeonhole principle
127:collision resistance
43:improve this article
387:Puzzle friendliness
527:10.1007/11535218_2
446:2012-04-21 at the
242:discrete logarithm
219:brute-force attack
207:
206:
133:: a hash function
540:Dodis, Yevgeniy.
361:digital signature
204:
129:is a property of
119:
118:
111:
93:
585:
557:
555:
553:
551:
546:
537:
531:
530:
520:
505:
499:
498:
496:
495:
489:
483:. Archived from
482:
473:
467:
460:
451:
431:
392:Collision attack
216:
214:
213:
208:
205:
203:
202:
193:
178:birthday paradox
114:
107:
103:
100:
94:
92:
51:
27:
19:
593:
592:
588:
587:
586:
584:
583:
582:
563:
562:
561:
560:
549:
547:
544:
538:
534:
521:. CRYPTO 2005.
518:
506:
502:
493:
491:
487:
480:
474:
470:
461:
454:
448:Wayback Machine
432:
425:
420:
397:Preimage attack
382:Birthday attack
378:
353:
337:
306:
297:
264:
254:
246:provably secure
198:
194:
192:
189:
186:
185:
115:
104:
98:
95:
52:
50:
40:
28:
17:
12:
11:
5:
591:
581:
580:
575:
559:
558:
532:
512:; Hongobo Yu.
510:Yiqun Lisa Yin
508:Xiaoyun Wang;
500:
468:
452:
434:Goldwasser, S.
422:
421:
419:
416:
415:
414:
409:
404:
399:
394:
389:
384:
377:
374:
373:
372:
368:
352:
349:
336:
333:
325:
324:
319:Pr < negl(
302:
293:
260:
253:
250:
201:
197:
117:
116:
31:
29:
22:
15:
9:
6:
4:
3:
2:
590:
579:
576:
574:
571:
570:
568:
543:
536:
528:
524:
517:
516:
511:
504:
490:on 2009-05-21
486:
479:
472:
465:
459:
457:
449:
445:
442:
439:
435:
430:
428:
423:
413:
410:
408:
405:
403:
400:
398:
395:
393:
390:
388:
385:
383:
380:
379:
369:
366:
362:
358:
357:
356:
348:
344:
340:
332:
330:
322:
318:
317:
316:
314:
310:
305:
301:
296:
292:
288:
284:
280:
276:
272:
268:
263:
259:
249:
247:
243:
239:
234:
230:
226:
222:
220:
199:
195:
183:
179:
174:
172:
168:
164:
160:
156:
152:
148:
144:
140:
136:
132:
128:
124:
113:
110:
102:
99:December 2009
91:
88:
84:
81:
77:
74:
70:
67:
63:
60: –
59:
55:
54:Find sources:
48:
44:
38:
37:
32:This article
30:
26:
21:
20:
548:. Retrieved
535:
514:
503:
492:. Retrieved
485:the original
471:
354:
345:
341:
338:
328:
326:
320:
312:
308:
303:
299:
294:
290:
286:
282:
278:
274:
270:
266:
261:
257:
255:
223:
181:
175:
166:
162:
158:
154:
150:
146:
142:
138:
134:
126:
123:cryptography
120:
105:
96:
86:
79:
72:
65:
53:
41:Please help
36:verification
33:
438:Bellare, M.
285:)| for any
567:Categories
494:2009-12-21
418:References
365:public key
315:, we have
252:Definition
69:newspapers
550:3 January
462:Pass, R.
351:Rationale
277:)| > |
556:, def 1.
444:Archived
376:See also
359:In some
289:, i.e.,
169:). The
83:scholar
145:where
85:
78:
71:
64:
56:
545:(PDF)
519:(PDF)
488:(PDF)
481:(PDF)
233:SHA-1
176:The "
90:JSTOR
76:books
552:2016
436:and
371:not.
231:and
161:) =
153:but
141:and
62:news
523:doi
240:or
229:MD5
121:In
45:by
569::
455:^
426:^
323:),
248:.
149:≠
125:,
554:.
529:.
525::
497:.
329:n
321:n
313:A
309:k
304:k
300:h
295:k
291:h
287:k
283:k
281:(
279:l
275:k
273:(
271:m
267:G
262:k
258:h
200:N
196:2
182:N
167:b
165:(
163:H
159:a
157:(
155:H
151:b
147:a
143:b
139:a
135:H
112:)
106:(
101:)
97:(
87:·
80:·
73:·
66:·
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
