[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.

http://en.wikipedia.org/wiki/Back_Orifice
http://www.iss.net/security_center/reference/vuln/BackOrifice.htm

"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))
          break;
        pos++;
        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.

Alexander



More information about the cryptography mailing list