[cryptography] Non-governmental exploitation of crypto flaws?

Solar Designer solar at openwall.com
Sun Nov 27 19:26:26 EST 2011

On Sun, Nov 27, 2011 at 10:14:48PM +0100, Florian Weimer wrote:
> ... attacks on malware encryption schemes by the AV industry.

A curious example of this is poor crypto in the original Back Orifice,
where, if I recall correctly, some IDS products would try to crack the
encryption key in real time to detect BO traffic on non-standard ports
or to confirm that traffic on the standard port is indeed BO.


"No false negatives are known for this signature. RealSecure can detect
BackOrifice traffic on all ports, with any password."

I actually optimized the algorithm myself at the time (based on a less
optimal implementation by a friend of mine), just for fun.  IIRC, I got
it to run in under 100 ms worst-case on my 533 MHz Alpha (which felt
like a very fast machine).  It did not actually have to try all keys, but
it could skip over entire blocks of known-wrong keys (PRNG seed values).

Oh, I found this optimization (turns out I still have a copy of the code):

  for (key = 2531011UL; key < 2531011UL + 0xCDCB0000UL * 214013UL; key += 214013UL) {
    diff = (match0 - (key & 0xFF0000UL)) & 0xFF0000UL;
    if ((diff -= 0x10000L) > 0)
      key += diff / 214013UL * 214013UL;
    else if (match0 == (key & 0xFF0000UL)) {
      hold = key;
      pos = 1;
      while (1) {
        if (match[pos] != ((hold = hold * 214013UL + 2531011UL) & 0xFF0000))
        if (pos == MAGICSTRINGLEN)
          return (key - 2531011UL) / 214013UL;

(Hmm, appears to run in under 3 ms on a current 2.5 GHz CPU.  Must have
been something like 15 ms to 30 ms on the Alpha, then.)

Many of the integer variables are 64-bit here.  IIRC, it's this line:
      key += diff / 214013UL * 214013UL;
that skipped blocks of keys.  There's further room for optimization here
(even this one line could be written better), but it was just an
unreleased hack.  As I mentioned above, others did presumably the same
thing for at least one commercial product.  Or maybe they used a table
lookups based algorithm.  IIRC, the seed value was 32-bit, which is too
small for real crypto anyway, but it could be large enough to make
real-time detection by IDS impractical at the time if key-skipping and
table lookups were not possible.

Indeed, this was not real crypto in many other aspects as well.


More information about the cryptography mailing list