Neil Schemenauer's Web Log

Debian has a pretty important vote happening right now. The ballot is complicated, some would say even poorly written. I agree with Daniel Burrows that the including both super-majority options and simple-majority options on a single ballot is problematic. It would have been better to have two votes, I think. Using Daniel's example, the first ballot would be

[ ] Choice 1: Omelette [3:1]
[ ] Choice 2: Quiche [3:1]
[ ] Choice 3: Further Discussion

If option 3 wins then the next ballot should be:

[ ] Choice 1: Toast
[ ] Choice 2: Further Discussion

While the Debian ballot is complicated, I don't think it requires people to vote strategically (which would be a failure of the voting system). As long as most people rank the "delay Lenny" option below the "don't delay" options then the "delay" option will not win. Thankfully we don't use first-past-the-post because this is a classic vote splitting ballot.

As a final note, I wish approval voting would gain more traction. The Condorcet method is obviously better than plurality but it's probably just too complicated to ever see wide spread adoption. Approval voting can be easily be done with a pencil and paper and still gives nice results. The Canadian Wheat Board recently had an election where they used IRV. IRV sounds like a good idea but it's more complicated that approval voting and has some nasty behavior in certain cases.

Update for 2010-07-25: The original code here was vulnerable to a timing attack. The old version of the code used == to compare the hashed passwords. I've updated the code to use a constant time compare. Bewarned there very well could be more bugs in this code.

This is a quick note on hashing user passwords. I fear that some people might still be doing this wrong. They might be storing plain-text passwords (yikes!) or they might use a hash that is vulnerable to brute force attacks. The following is an example of the algorithm I'm using. Note that for new code sha1 should be replaced by a stronger hash function (e.g. sha256) and perhaps _HASH_ROUNDS should be adjusted.

def constant_time_compare(a, b):
    """A constant time comparison function for two strings. Returns
    True if the strings are equal.
    """
    result = 0 if len(a) == len(b) else 1
    for x, y in zip(a, b):
        result |= ord(x) ^ ord(y)
    return result == 0

class User(Persistent):
   """
    Instance attributes:
      password_hash : str | None
        if None then logins are disabled, see _encrypt() for details on hashing
      password_salt : str
        a noonce 
    """

    _SALT_LENGTH = 32 # 256 bits
    _HASH_ROUNDS = 2**16

    ...

    def _encrypt(self, password):
        """(password : str | unicode) -> str
        """
        # salt and stretch password as recommended by Ferguson & Schneier in
        # "Practical Cryptography"
        if isinstance(password, unicode):
            password = password.encode('utf-8')
        h = ''
        assert self._HASH_ROUNDS > 0
        for i in range(self._HASH_ROUNDS):
            h = hashlib.sha1(h + self.password_salt + password).digest()
        return h

    def set_password(self, password):
        self.password_salt = os.urandom(self._SALT_LENGTH)
        self.password_hash = self._encrypt(password)

    def validate_password(self, password):
        """(password : str) -> bool
        """
        if self.password_hash is None:
            return False
        else:
            return constant_time_compare(self._encrypt(password),
                                         self.password_hash)

There is a useful discussion on stackoverflow.com along with some sample Python code. Note that using HMAC instead of concatenation doesn't buy any security if you assume the salt is not secret. Also, the random_bytes() function in the sample code is lame since it's a poor nonce.