C[omp]ute

From: andrew cooke <andrew@...>

Date: Mon, 13 May 2013 11:16:42 -0400

This was preliminary work for the StackOverflow answer at
http://stackoverflow.com/questions/11096134/print-a-binary-tree-on-its-side/16680023#16680023
- I did it while on holiday (installed Python on Mum's laptop :o) and then
posted the answer when I got home.  I have modified these posts since first
writing them to improve the code and explanation a little.

To be honest, it's not very exciting code - just careful bookkeeping and the
kind of recursive approach you'd expect, merging results from sub-trees.

Here are some results (I've named the leaves according to their location,
which helps understand what is happening, I hope):

 5 nodes
    /rr
   /\rl
  / /lrr
  \/\lrl
   \ll

 20 nodes
	    /rrrrr
	   /\rrrrl
	  /\rrrl
	 /\/rrlr
	/  \rrll
       /   /rlrrr
      /\  /\/rlrrlr
     /  \/\ \rlrrll
    /    \ \rlrl
   /      \/rllr
  /        \rlll
  \        /lrrrr
   \      /\lrrrl
    \    /\lrrl
     \  / /lrlr
      \/\/ /lrllrr
       \ \/\lrllrl
	\ \lrlll
	 \/llr
	  \lll

And the code follows.

Andrew



#!/usr/local/bin/python3.3

from itertools import chain
from random import randint


# first, some support routines.  these assume that a tree is either a string
# leaf value, or a tuple (pair) of subnodes.

def leaf(t):
    '''is the given node a leaf?'''
    return isinstance(t, str)

def random(n):
    '''generate a random tree with n nodes (n > 1)'''
    def extend(t):
        if leaf(t):
            return (t+'l', t+'r')
        else:
            l, r = t
            if randint(0, 1): return (l, extend(r))
            else: return (extend(l), r)
    t = ''
    for _ in range(n-1): t = extend(t)
    return t


# next, the formatting itself.  this is not that exciting - a recursive 
# descent to the leaves and then a merging of sub-trees on the returns.
# the hard part is just the book-keeping.

def format(t):
    '''format the tree (returns a multi-line string reprn)'''

    def pad(label, prefix, spaces, previous):
        '''add spaces between / (or \) and the previous line contents.
           change ' ' to label to see what logic is used where'''
        return prefix + (' ' * spaces) + previous

    def merge(l, r):
        '''merges the two sub-trees to generate the fragment for the
           combined node.  a fragment is (above, below, lines) where
           above is number of lines above root, below below root, and
           lines is an iterator over each partial line.'''
        l_above, l_below, l_lines = l
        r_above, r_below, r_lines = r
        gap = r_below + l_above
        gap_above = l_above  # this balances the result (see post text)
        gap_below = gap - gap_above

        def lines():
            '''the actual mergin of lines.  there are six different cases,
               handled in turn.'''
            for (i, line) in enumerate(chain(r_lines, l_lines)):
                if i < r_above:
                    # we already have 'sloped' data above where we are joining
                    yield line
                elif i - r_above < gap_above:
                    # we are in the upper branch region, joined by a / symbol
                    if i < r_above + r_below:
                        # are we filling the increasing gap between the new 
                        # / branch and the existing tree that has a \ shaped 
                        # boundary?
                        yield pad('A', '/', 2 * (i - r_above), line)
                    else:
                        # or are we in the constant sized gap between the 
                        # new / branch and the upper / shaped boundary of the 
                        # lower sub-node?
                        yield pad('B', '/', 2 * gap_below - 1, line)
                elif i - r_above - gap_above < gap_below:
                    # we are in the lower branch region, joined by a \ symbol
                    if i < r_above + r_below:
                        # are we overlapping the \ shaped boundary of the 
                        # upper sub-node?
                        yield pad('C', '\\', 2 * gap_above - 1, line)
                    else:
                        # or are we in the gap between the new \ and the 
                        # / shaped edge of the lower sub-node?
                        spaces = 2 * (r_above + gap_above + gap_below - i - 1)
                        yield pad('D', '\\', spaces, line)
                else:
                    # we already ave 'sloped' data below where we are joining
                    yield line
        return (r_above + gap_above, gap_below + l_below, lines())

    def descend(left, t):
        '''descend to leaf nodes, where we know what the fragments are
           (just the leaf contents) and then merge nodes on return.'''
        if leaf(t):
            if left:
                return (1, 0, [t])
            else:
                return (0, 1, [t])
        else:
            l, r = t
            return merge(descend(True, l), descend(False, r))

    def flatten(t):
        '''add left-hand spacing to the final tree.'''
        above, below, lines = t
        for (i, line) in enumerate(lines):
            if i < above: yield (' ' * (above - i - 1)) + line
            else: yield (' ' * (i - above)) + line

    # put it all together...
    return '\n'.join(flatten(descend(True, t)))


if __name__ == '__main__':
    for n in range(1,20,3):
        tree = random(n)
        print(tree)
        print(format(tree))

Python's sad, unimaginative Enum

From: andrew cooke <andrew@...>

Date: Sat, 11 May 2013 11:03:33 -0400

Python is about to get an Enum.  See http://www.python.org/dev/peps/pep-0435/

And it's sad.

It's not awful.  It just fails to do anything particularly well - it's an
awkward compromise whose only real achievement is not doing anything new.

What would you expect a Pythonic enum to look like?

  class Colour(Enum):
      red
      green

  > print(Colour.red == Colour.green)
  false

That's about the minimum, right?  But it doesn't do that.  The above would
require new syntax, so instead you have to define values:

  class Colour(Enum):
      red = 1
      green = 1

Still, at least the mistake above would raise an error.  Wouldn't it?  Nope.
That's a feature.  If you mess up on the non-optional values then you get
"aliases".  Because that's something I've waited all my life for, while I
never make mistakes...  Or something.  The something being that they are
smoking fucking crack.

But you could just as well type:

  class Colour:
      red = 1
      green = 2

so what does Enum get you?  It provides a bit of metaclass goop to let you
iterate over values, etc.  Whoop.

So, you go hunting around in the docs to see if there's any way at all of
avoiding the need to assign values manually.  And there is:

  Colour = Enum('Colour', 'red, green')

which suffers from the same problems as namedtuples:
  - you need to repeat the class name (in a string, which your IDE is
    unlikely to check)
  - the parameters are themselves in a string, which your IDE is 
    unlikely to parse and provide in auto-complete (they can be separate
    strings, in a sequence, but that doesn't really help).

Now if two potentially useful library classes are suffering from the same
problems than isn't that a BIT OF A HINT to try make things better?  Nope.  It
just shows how important it is to not be imaginative.  Or something (crack).

And it gets worse.  What values do you think the above provides?

Strings?  That would makes sense (red = 'red'), in that it would display
nicely and is going to provide easy to debug values.  So nope.

Integers from zero?  I mean that's how Python counts indices and there's "only
one way to do it" so that's how Python counts enums, right?  Nope.

OK, so bit fields?  That way we can do cool Colour.red | Colour.green and
make the C programmers feel at home?  Nope.

Give up?  I'll tell you.  It counts from 1.  Presumably because it's really
common to use the "if not enum" idiom.  In someone's crack-addled dreams.


Like I said at the start.  None of this is really awful.  It's just lame.
It's design by committee that finds the least offensive, least imaginative,
least useful solution.

One big pile of meh.

Andrew

Permalink

Work, Exhaustion, Vacation

From: andrew cooke <andrew@...>

Date: Wed, 8 May 2013 09:09:33 -0400

Being tired is a common symptom of MS.  With vacations coming up I took care
to tell one client I needed to have as much time as possible to complete.  At
the same time I was balancing another project on the side, but that was almost
done.  So the plan was to get both in a good state before the holiday.

And that, as far as it went, worked.

But one client decided to test a project that was completed three months ago
the day before I finished.  I fixed one major issue (we had the wrong tarball
archived - probably my fault), avoided another (client and server cannot run
on the same machine due to hardware limitations), and helped with a third.

But then time ran out - I was exhausted, I needed to sleep, I had a trip to
prepare for.

So that's how it goes.  I plan in advance and I get a good job done.  But last
minute rushes just aren't going to make it any more.  Sorry.

Andrew

Permalink

VirtualBox with Centos 6.3 to 6.4, client

From: andrew cooke <andrew@...>

Date: Tue, 7 May 2013 12:46:50 -0400

It hangs at the end of boot.  There's a solution at
http://www.techpository.com/?page_id=1487

In short:

 - At start of boot, hit any key, then "a", then append "single" and
   hit return.

 - As root, zap /etc/X11/xorg.conf and then reboot.

Andrew

Permalink

Matasano - Programming Lessons Learned

From: andrew cooke <andrew@...>

Date: Sun, 5 May 2013 23:07:47 -0400

I just finished the crypto challenge.

I (vaguely) remember, many years ago, sitting down to write a library that
would help me with cryptanalysis (I've always be interested in codes and the
like).

Back then I wasn't (I hope) as good a programmer as I am now.  Or, at least,
not as experienced.  And I remember getting stuck in analysis paralysis quite
quickly.  The project never got very far.

Looking at the code for the crypto challenge, I have effectively done what I
set out to do years ago.  And I think there are some lessons to learn from
that.

Most obvious, a general point about software development - it's much easier to
write code when you're solving a real problem (rather than trying to develop
something to address an abstract set of issues).  This is much of the essence
of "Agile".

But there are also some specific details that I am pleased with:

 - I used a very general approach for "rating" the results from using various
   keys, based on pluggable tokenizers and dictionaries of scores.  This let
   me use the same code for letter and word frequency analysis.  The Python
   Counter class was particularly useful, as was a simple hack to print the
   contents as a histogram (on it's side, each "column" a row of stars).

 - Coroutines as actors worked well for simulating protocols
   http://www.acooke.org/cute/UsingCorou0.html

 - Higher order functions worked nicely for constructing operations from
   simpler primitives - both building cipher modes from ECB and hashes via
   Merkel Damgard http://www.acooke.org/cute/PurePython0.html

And one where I could have done better:

 - I didn't find a good balance between generators and sequences.  Generators
   are great for working with sequences of bits, bytes, words.  And for
   composing pipelines.  But at a higher level (eg output from hashes) you
   want byte arrays that you can add together like strings.  Instead I let
   generators "get too high" and then had to explicitly add bytes().

Andrew

Permalink

PDF to HTML

From: andrew cooke <andrew@...>

Date: Sun, 5 May 2013 12:32:41 -0400

https://github.com/coolwanglu/pdf2htmlEX

Look at the first example.  Mind-blowing.

Andrew

Permalink

Why RSA Works

From: andrew cooke <andrew@...>

Date: Sat, 4 May 2013 16:25:23 -0400

I've been implementing and cracking RSA, but, until now, it's not been clear
to me exactly why it works.  Or why it seems to be commutative (which is why
you can sign too).  Or why the totient - (p-1)*(q-1) - is used.

All those questions were answered, plop (as they say in Chile), when I saw
equation 1 of this post:

http://doctrina.org/Why-RSA-Works-Three-Fundamental-Questions-Answered.html

Aha!  Suddenly it all makes much more sense... :o)


If your head is not already full of RSA then you might want to start with the
preceding post, which describes RSA in practice:

http://doctrina.org/How-RSA-Works-With-Examples.html

Andrew

Permalink

Dreaming of Death

From: andrew cooke <andrew@...>

Date: Fri, 3 May 2013 21:29:49 -0400

You probably want to skip this.  Writing more for myself, just to clear my
head.

Last night (this morning, I think, just before I woke) I dreamt that I killed
myself.  I found myself, dead, and picked myself up.  I was full of
compassion, but not sadness.

I don't really understand why I had this dream now.  I was much more worried
about dying back in November.  Things are much better now.

What worries me is that a possible side-effect of the meds is suicidal
thoughts (and, well, suicide).  Strong stuff.

Andrew

Permalink

Using Coroutines In Protocol Simulations

From: andrew cooke <andrew@...>

Date: Mon, 29 Apr 2013 21:14:30 -0400

I don't want to sound like a shill, but I am having a great time with the
Matasano crypto challenges http://www.matasano.com/articles/crypto-challenges/
and I wanted to share a neat trick.

So I just got DH key exchange working.  Which is awesome - I had no idea it
was so easy.  But what made me extra-happy was the way that I coded the two
agents that were communicating.  I wrote each as a co-routine.

So my code looked a little like this:

    def alice(ptext):
        my_key = random()
        bobs_key = yield my_key
        joint_key = f(my_key, bobs_key)
        yield encrypt(ptext, joint_key)

    def bob():
        alices_key = yield
        my_key = random()
	ctext = yield my_key
        joint_key = f(my_key, alices_key)
        ptext = decrypt(ctext, joint_key)
	print('bob received', ptext)

    communicate(alice('hiya sexy'), bob())

If you're confused by that, all you need to know, really, is that each "yield"
is a message send.  So alice sends her key to bob, bob receives it (the value
returned from the first yield in bob), and replies with his own key, which
alice receives. etc etc.

Isn't that a cool way of writing communicating processes?

Here's the definition of communicate.  It will chain any number of agents
(because just maybe there's a mallory to add later...), passing messages from
left to right, then right to left, until done.

    def communicate(*agents):
	try:
	    data = lmap(next, agents)[0]  # prime, and receive initial data
	    while True:
		for receiver in agents[1:]:
		    print('data', data)
		    data = receiver.send(data)
		agents = list(reversed(agents))
	except StopIteration: return

and lmap is list(map) (something I always have defined in Python 3).

Andrew

PS Again, the above reveals neither question nor solution from the challenge,
so I believe it is OK.

PPS One reason I think this approach is so cool (apart from it being compact
and easy to read) is that the agents are completely decoupled from the
communcations process.  So adding another agent to do a man-in-the-middle
attack doesn't require any modification to bob or alice.

Permalink

Pure Python SHA1 and MD4 Implementations

From: andrew cooke <andrew@...>

Date: Sun, 28 Apr 2013 10:01:04 -0400

I am working through the Matasano Crypto Challenges -
http://www.matasano.com/articles/crypto-challenges/ - which I would recommend
to anyone interested in crypto.

Although they repeatedly ask not to post solutions online, they do ask (in
part 4, I think) for you to find (rather than implement) implementations of
SHA1 and MD4.  So I hope that it is OK for me to post these.

The two implementations are based on code at
https://raw.github.com/ajalt/python-sha1/master/sha1.py and
http://www.oocities.org/rozmanov/python/md4.html - the latter of those is
licensed under the LGPL and so the derivative work below is licensed the same
way.

While I am grateful to the two authors above (AJ Alt and Dmitry Rozmanov) I
have *extensively* reworked the code.  I hope that the implementation below
helps show the common structure shared by both.  And if you thought "MD
padding" meant "Message Digest padding" then you should read
http://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction

Also, note that I use generators whenever possible, so you may need to wrap
things in bytes(...) to get a byte array.


First, a few library routines:

def little_endian_bytes(words, n):
    '''convert n-byte words to bytes (little endian)'''
    for word in words:
        for _ in range(n):
            yield word & 0xff
            word >>= 8

def big_endian_bytes(words, n):
    '''convert n-byte words to bytes (big endian)'''
    for word in words:
        yield from reversed(list(little_endian_bytes([word], n)))

def big_endian_words(b, n):
    '''convert bytes into n-byte words (big endian)'''
    for g in grouped(b, n):
        w = 0
        for b in g:
            w = w << 8 | b
        yield w

def little_endian_words(b, n):
    '''convert bytes into n-byte words (little endian)'''
    for g in grouped(b, n):
        yield from big_endian_words(reversed(g), n)


Now the crypto:

import struct
from cpals.common.bit import big_endian_bytes, little_endian_bytes, little_endian_words


# https://raw.github.com/ajalt/python-sha1/master/sha1.py
# (modified)

# http://www.oocities.org/rozmanov/python/md4.html
# Copyright (C) 2001-2002  Dmitry Rozmanov (LGPL)
# modified


def left_rotate(n, b):
    return ((n << b) | ((n & 0xffffffff) >> (32 - b))) & 0xffffffff

def md_pad_64(message, length_to_bytes, fake_byte_len=None):
    original_byte_len = len(message)
    message += b'\x80'
    message += b'\x00' * ((56 - (original_byte_len + 1) % 64) % 64)
    original_bit_len = (fake_byte_len if fake_byte_len else original_byte_len) * 8
    message += bytes(length_to_bytes(original_bit_len))
    return message

def make_md_hash_64(compress, state_to_hash, length_to_bytes):
    def md_hash(message, fake_byte_len=None, state=None):
        message = md_pad_64(message, length_to_bytes, fake_byte_len=fake_byte_len)
        for i in range(0, len(message), 64):
            state = compress(message[i:i+64], state)
        return state_to_hash(state)
    return md_hash


def sha1_compress(block, state=None):

    if not state: state = [0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0]
    a, b, c, d, e = h0, h1, h2, h3, h4 = state

    w = [0] * 80
    # break chunk into sixteen 32-bit big-endian words w[i]
    for j in range(16):
        w[j] = struct.unpack('>I', block[j*4:j*4 + 4])[0]
    # extend the sixteen 32-bit words into eighty 32-bit words:
    for j in range(16, 80):
        w[j] = left_rotate(w[j-3] ^ w[j-8] ^ w[j-14] ^ w[j-16], 1)

    for i in range(80):
        if i < 20:
            f = d ^ (b & (c ^ d)) # use alternative 1 for f from FIPS PB 180-1 to avoid ~
            k = 0x5A827999
        elif 20 <= i < 40:
            f = b ^ c ^ d
            k = 0x6ED9EBA1
        elif 40 <= i < 60:
            f = (b & c) | (b & d) | (c & d)
            k = 0x8F1BBCDC
        elif 60 <= i:
            f = b ^ c ^ d
            k = 0xCA62C1D6
        a, b, c, d, e = ((left_rotate(a, 5) + f + e + k + w[i]) & 0xffffffff, a, left_rotate(b, 30), c, d)

    return [(h0 + a) & 0xffffffff, (h1 + b) & 0xffffffff, (h2 + c) & 0xffffffff, (h3 + d) & 0xffffffff, (h4 + e) & 0xffffffff]

SHA1 = make_md_hash_64(sha1_compress, lambda state: big_endian_bytes(state, 4), lambda length: big_endian_bytes([length], 8))


def f(x, y, z): return x & y | ~x & z
def g(x, y, z): return x & y | x & z | y & z
def h(x, y, z): return x ^ y ^ z

def f1(a, b, c, d, k, s, X): return left_rotate(a + f(b, c, d) + X[k], s)
def f2(a, b, c, d, k, s, X): return left_rotate(a + g(b, c, d) + X[k] + 0x5a827999, s)
def f3(a, b, c, d, k, s, X): return left_rotate(a + h(b, c, d) + X[k] + 0x6ed9eba1, s)

def md4_compress(block, state=None):

    if not state: state = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476]
    a, b, c, d = h0, h1, h2, h3 = state

    x = list(little_endian_words(block, 4))

    a = f1(a,b,c,d, 0, 3, x)
    d = f1(d,a,b,c, 1, 7, x)
    c = f1(c,d,a,b, 2,11, x)
    b = f1(b,c,d,a, 3,19, x)
    a = f1(a,b,c,d, 4, 3, x)
    d = f1(d,a,b,c, 5, 7, x)
    c = f1(c,d,a,b, 6,11, x)
    b = f1(b,c,d,a, 7,19, x)
    a = f1(a,b,c,d, 8, 3, x)
    d = f1(d,a,b,c, 9, 7, x)
    c = f1(c,d,a,b,10,11, x)
    b = f1(b,c,d,a,11,19, x)
    a = f1(a,b,c,d,12, 3, x)
    d = f1(d,a,b,c,13, 7, x)
    c = f1(c,d,a,b,14,11, x)
    b = f1(b,c,d,a,15,19, x)

    a = f2(a,b,c,d, 0, 3, x)
    d = f2(d,a,b,c, 4, 5, x)
    c = f2(c,d,a,b, 8, 9, x)
    b = f2(b,c,d,a,12,13, x)
    a = f2(a,b,c,d, 1, 3, x)
    d = f2(d,a,b,c, 5, 5, x)
    c = f2(c,d,a,b, 9, 9, x)
    b = f2(b,c,d,a,13,13, x)
    a = f2(a,b,c,d, 2, 3, x)
    d = f2(d,a,b,c, 6, 5, x)
    c = f2(c,d,a,b,10, 9, x)
    b = f2(b,c,d,a,14,13, x)
    a = f2(a,b,c,d, 3, 3, x)
    d = f2(d,a,b,c, 7, 5, x)
    c = f2(c,d,a,b,11, 9, x)
    b = f2(b,c,d,a,15,13, x)

    a = f3(a,b,c,d, 0, 3, x)
    d = f3(d,a,b,c, 8, 9, x)
    c = f3(c,d,a,b, 4,11, x)
    b = f3(b,c,d,a,12,15, x)
    a = f3(a,b,c,d, 2, 3, x)
    d = f3(d,a,b,c,10, 9, x)
    c = f3(c,d,a,b, 6,11, x)
    b = f3(b,c,d,a,14,15, x)
    a = f3(a,b,c,d, 1, 3, x)
    d = f3(d,a,b,c, 9, 9, x)
    c = f3(c,d,a,b, 5,11, x)
    b = f3(b,c,d,a,13,15, x)
    a = f3(a,b,c,d, 3, 3, x)
    d = f3(d,a,b,c,11, 9, x)
    c = f3(c,d,a,b, 7,11, x)
    b = f3(b,c,d,a,15,15, x)

    return [(h0 + a) & 0xffffffff, (h1 + b) & 0xffffffff, (h2 + c) & 0xffffffff, (h3 + d) & 0xffffffff]

MD4 = make_md_hash_64(md4_compress, lambda state: little_endian_bytes(state, 4), lambda length: little_endian_bytes([length], 8))


Enjoy,
Andrew

Permalink

Ubuntu on VirtualBox

From: andrew cooke <andrew@...>

Date: Tue, 23 Apr 2013 14:28:56 -0300

Ubuntu 12.04-2 does not install cleanly on the latest VirtualBox (4.12.2).

Instead, install 12.04 (the initial release) and DO NOT UPDATE KERNEL
packages (if you really want to, snapshot first).

Andrew

Permalink

Starting TOR as a service on OpenSuse 12.3

From: andrew cooke <andrew@...>

Date: Thu, 18 Apr 2013 22:04:41 -0300

I wanted to install Tor and run it as a bridge for others.

It's easy to build and install Tor from source -
https://www.torproject.org/download/download-unix.html.en - and the config
file is pretty self-explanatory.

But it's not clear how to run it as a service (I'm only using it as a bridge -
I don't plan to use it myself).  Eventually I found
https://trac.torproject.org/projects/tor/ticket/8368 which I adapted as
follows:

  # cat /etc/systemd/system/tor.service
  [Unit]
  Description = Anonymizing overlay network for TCP
  After = syslog.target network.target nss-lookup.target

  [Service]
  Type = simple
  ExecStart = /usr/local/bin/tor --runasdaemon 0 -f /usr/local/etc/tor/torrc --quiet
  ExecReload = /bin/kill -HUP ${MAINPID}
  ExecStop = /bin/kill -INT ${MAINPID}
  TimeoutSec = 30
  Restart = on-failure
  LimitNOFILE = 4096

  [Install]
  WantedBy = multi-user.target

Which works just fine:

  # systemctl start tor.service
  #

Except that it is running as root.  I am not sure how to fix that part.

Andrew

Permalink