Bitbashing (Posts about algorithms)https://randombit.net/bitbashing/categories/algorithms.atom2019-08-02T22:27:07ZJack LloydNikolaAlgorithmic Complexity Attacks on Allocatorshttps://randombit.net/bitbashing/posts/allocation.html2006-11-01T00:00:00-05:002006-11-01T00:00:00-05:00Jack Lloyd<div><p>A few years back some researchers presented the concept of performing
denial of service through <a class="reference external" href="http://www.cs.rice.edu/~scrosby/hash/">algorithmic complexity attacks</a>, which essentially cause
pathological behavior in data structures like hash tables through
carefully chosen inputs.</p>
<p><a href="https://randombit.net/bitbashing/posts/allocation.html">Read more…</a> (1 min remaining to read)</p></div>Finding Equivalences of Boolean Functionhttps://randombit.net/bitbashing/posts/booleans.html2006-08-30T00:00:00-04:002006-08-30T00:00:00-04:00Jack Lloyd<div><p>A fairly common class of functions in crypto are functions mapping
{0,1}<sup>3</sup> onto {0,1}. In particular, these show up a lot in hash
functions derived from MD4, including MD5, SHA-1, RIPEMD, and
SHA-512. These range in complexity from simple three-term expressions
like "(A xor B xor C)" to functions like "((A and B) or (C and (A or
B)))". One interesting and important difference between these two
functions becomes very important when you consider how to implement
these functions on an x86 (or x86-64) processor. The x86 uses
two-operand instructions, and has very few registers, so computing
something like "(A and B) xor (not(A) and C)", which requires two
temporaries (one to hold A and B, the other (not(A) and C)) might
require you to spill values to the stack. Often, that means a major
performance hit. Finding an alternate form for this function that only
requires fewer temporary registers could be a major benefit. Obviously
finding these equivalences could be done by hand, but having a
computer do it seemed both faster and more interesting.</p>
<p><a href="https://randombit.net/bitbashing/posts/booleans.html">Read more…</a> (2 min remaining to read)</p></div>