<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi Joe,<div><br></div><div>There's one huge difference between page deduplication and object deduplication: Page size is small and predictable, whereas object size is not. Given this, full compares would not be a good way to implement performant object deduplication in swift.</div><div><br></div><div>Thanks,</div><div><br></div><div><br></div><div>Maru<br><div><br><div><div>On 2012-03-10, at 9:57 AM, Joe Gordon wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div><div>Paulo, Caitlin, </div><div><br></div><div><br></div><div>Can SHA-1 collisions be generated? If so can you point me to the article? </div></div><div><br></div><div>Also why compare hashes in the first place? Linux 'Kenel Samepage Merging', which does page deduplication for KVM, does a full compare to be safe [1]. Even if collisions can't be generated, what are the odds of a collision (for SHA-1 and SHA-256) happening by chance when using Swift at scale? </div>
<div><br></div><div><br></div><div>best,</div><div>Joe Gordon</div><blockquote class="gmail_quote" style="margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div lang="EN-US" link="blue" vlink="purple"><div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><u></u><u></u></div></div></div></blockquote><div><br></div><div><br></div><div>
<br></div>[1] <a href="http://www.linux-kvm.com/sites/default/files/KvmForum2008_KSM.pdf">http://www.linux-kvm.com/sites/default/files/KvmForum2008_KSM.pdf</a><div><br></div><div><br><div class="gmail_quote">On Fri, Mar 9, 2012 at 4:44 PM, Caitlin Bestler <span dir="ltr"><<a href="mailto:Caitlin.Bestler@nexenta.com">Caitlin.Bestler@nexenta.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="EN-US" link="blue" vlink="purple">
<div><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Paulo,<u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">I believe you’ll find that we’re thinking along the same lines. Please review my proposal at
</span><a href="http://etherpad.openstack.org/P9MMYSWE6U" target="_blank">http://etherpad.openstack.org/P9MMYSWE6U</a><u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">One quick observation is that SHA-1 is totally inadequate for fingerprinting objects in a public object store. An attacker could easily<u></u><u></u></p><p class="MsoNormal">predict the fingerprint of content likely to be posted, generate alternate content that had the same SHA-1 fingerprint and pre-empt<u></u><u></u></p><p class="MsoNormal">the signature. For example: an ISO of an open source OS distribution. If I get my false content with the same fingerprint into the<u></u><u></u></p><p class="MsoNormal">repository first then everyone who downloads that ISO will get my altered copy.</p></div></div></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="EN-US" link="blue" vlink="purple"><div><p class="MsoNormal"><u></u><u></u></p><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal">SHA-256 is really needed to make this type of attack infeasible.</p></div></div></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-US" link="blue" vlink="purple">
<div><p class="MsoNormal"> <u></u></p><p class="MsoNormal">I also think that distributed deduplication works very well with object versioning. Your comments on the proposal cited above
<u></u><u></u></p><p class="MsoNormal">would be great to hear.<span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> openstack-bounces+caitlin.bestler=<a href="mailto:nexenta.com@lists.launchpad.net" target="_blank">nexenta.com@lists.launchpad.net</a> [mailto:<a href="mailto:openstack-bounces%2Bcaitlin.bestler" target="_blank">openstack-bounces+caitlin.bestler</a>=<a href="mailto:nexenta.com@lists.launchpad.net" target="_blank">nexenta.com@lists.launchpad.net</a>]
<b>On Behalf Of </b>Paulo Ricardo Motta Gomes<br>
<b>Sent:</b> Thursday, March 08, 2012 1:19 PM<br>
<b>To:</b> <a href="mailto:openstack@lists.launchpad.net" target="_blank">openstack@lists.launchpad.net</a></span></p><div class="im"><br>
<b>Subject:</b> [Openstack] Enabling data deduplication on Swift<u></u><u></u></div><div><br class="webkit-block-placeholder"></div><p class="MsoNormal"><u></u> <u></u></p>
<div><p class="MsoNormal">Hello everyone,<u></u><u></u></p>
</div><div><div></div><div class="h5">
<div><p class="MsoNormal"><u></u> <u></u></p>
</div>
<div><p class="MsoNormal">I'm a student of the European Master in Distributed Computing (EMDC) currently working on my master thesis on distributed content-addressable storage/deduplication.<u></u><u></u></p>
</div>
<div><p class="MsoNormal"><u></u> <u></u></p>
</div>
<div><p class="MsoNormal">I'm happy to announce I will be contributing the outcome of my thesis work to OpenStack by enabling both object-level and block-level deduplication functionality on Swift (<a href="https://answers.launchpad.net/swift/+question/156862" target="_blank">https://answers.launchpad.net/swift/+question/156862</a>).<u></u><u></u></p>
</div>
<div><p class="MsoNormal"><u></u> <u></u></p>
</div>
<div><p class="MsoNormal">I have written a detailed blog post where I describe the initial architecture of my solution: <a href="http://paulormg.com/2012/03/05/enabling-deduplication-in-a-distributed-object-storage/" target="_blank">http://paulormg.com/2012/03/05/enabling-deduplication-in-a-distributed-object-storage/</a><u></u><u></u></p>
</div>
<div><p class="MsoNormal"><u></u> <u></u></p>
</div>
<div><p class="MsoNormal">Feedback from the OpenStack/Swift community would be very appreciated.<u></u><u></u></p>
</div>
<div><p class="MsoNormal"><u></u> <u></u></p>
</div>
<div><p class="MsoNormal">Cheers,<u></u><u></u></p>
</div>
<div><p class="MsoNormal"> <u></u><u></u></p>
</div>
<div><p class="MsoNormal">Paulo<u></u><u></u></p>
</div>
<div><p class="MsoNormal"><u></u> <u></u></p>
</div><p class="MsoNormal">-- <br>
European Master in Distributed Computing - <a href="http://www.kth.se/emdc" target="_blank">
www.kth.se/emdc</a><span style="font-family:"Arial","sans-serif""><br>
Royal Institute of Technology - KTH</span><u></u><u></u></p>
<div><p class="MsoNormal"><span style="font-family:"Arial","sans-serif"">Instituto Superior Técnico - IST</span><u></u><u></u></p>
</div>
<div><p class="MsoNormal"><span style="font-family:"Arial","sans-serif""><a href="http://paulormg.com/" target="_blank">http://paulormg.com</a></span><u></u><u></u></p>
</div>
</div></div></div>
</div>
<br>_______________________________________________<br>
Mailing list: <a href="https://launchpad.net/~openstack" target="_blank">https://launchpad.net/~openstack</a><br>
Post to : <a href="mailto:openstack@lists.launchpad.net">openstack@lists.launchpad.net</a><br>
Unsubscribe : <a href="https://launchpad.net/~openstack" target="_blank">https://launchpad.net/~openstack</a><br>
More help : <a href="https://help.launchpad.net/ListHelp" target="_blank">https://help.launchpad.net/ListHelp</a><br>
<br></blockquote></div><br></div>
_______________________________________________<br>Mailing list: <a href="https://launchpad.net/~openstack">https://launchpad.net/~openstack</a><br>Post to : <a href="mailto:openstack@lists.launchpad.net">openstack@lists.launchpad.net</a><br>Unsubscribe : <a href="https://launchpad.net/~openstack">https://launchpad.net/~openstack</a><br>More help : <a href="https://help.launchpad.net/ListHelp">https://help.launchpad.net/ListHelp</a><br></blockquote></div><br></div></div></body></html>