Damm algorithm | Hacker News Reader

Damm algorithm

en.wikipedia.org

75 pointstkmcc15 comments

The Damm algorithm is an amazingly useful algorithm. I put together a Base32 version that I use for checking passwords that users enter [1]. It is only in C and PHP right now - I need to get around to porting it javascript [2].

[1] http://www.tillett.info/2014/06/12/base32-implementation-of-...

[2] https://github.com/DanielTillett/Damm32

Question, in what context is it even possible, or advisable, to catch mistyped passwords?

Whenever you want to catch user errors client side rather than server side. It does not remove the need for security server side, but in my case it allows me to simplify the security aspects of my service and allow me to immediately drop any connection that is not using a potentially valid password. If a potentially valid password has been received then I do further checks on the actual password. Basically defence in layers.

Another potential use is for checking coupon codes client side. Of course a JavaScript port would be good for this.

Your Base32 alphabet only has 31 characters.

    >>> len("23456789abcdefghjkmnpqrstuvwxyz")
    31
    >>> (26 + 10) - 5  # a-z0-9, remove 1il0O
    31

Sure as I am wanting to avoid letters/number that can be confused by an user. You can change the encoding used to whatever you like. You can use less than 32 characters if you wish.

Edit. I do agree that I should make this clearer since if someone uses less than 31 characters then they will run into problems if they don't update my code.

point is, it's not base32 if there are 31 characters in the alphabet.

The code is base32 - it is just that I am not using one of the characters. If someone needs base32 they can add back one of the characters I removed and it would be fine.

Call it what you like, but it's base-31 and your name is misleading.

The code is base32 I just choose to never use one of the possible base32 digits. The way the Damm algorithm works this is fine to do.

Since so much of the discussion on this was about me using 31 characters in my encoding scheme rather than 32 (this is fine to do with the Damm algorithm) I have updated my code to make this clearer. I have also changed the code to make easier for someone to change the encoding if they don't like my scheme.

Took me at least 1 minute to notice that it was not "damn", which was quite puzzling me...

yeah I was kind of hoping this was an elaborate wikipedia joke article

So this is an improvement on the Luhn algorithm which is used for credit cards?

Pretty much.

First there's the Luhn algorithm, which "will detect any single-digit error, as well as almost all transpositions of adjacent digits. It will not, however, detect transposition of the two-digit sequence 09 to 90 (or vice versa). It will detect 7 of the 10 possible twin errors (it will not detect 22 ↔ 55, 33 ↔ 66 or 44 ↔ 77)." [0]

Then came the Verhoeff algorithm, which "was the first decimal check digit algorithm which detects all single-digit errors, and all transposition errors involving two adjacent digits, which was at the time thought impossible with such a code." [1]

The Damm algorithm was developed in 2004 and was a further improvement:

> The Damm algorithm is similar to the Verhoeff algorithm. It too will detect all occurrences of the two most frequently appearing types of transcription errors,[1] namely altering one single digit, and transposing two adjacent digits (including the transposition of the trailing check digit itself and the digit preceding it). But the Damm algorithm has the benefit that it makes do without the dedicatedly constructed permutations and its position specific powers being inherent in the Verhoeff scheme. Furthermore, a table of inverses can be dispensed with provided all main diagonal entries of the operation table are zero.

> The Damm algorithm does not suffer from exceeding the number of 10 possible values, resulting in the need for using a non-digit character (as the X in the 10-digit ISBN check digit scheme).

> Prepending leading zeros does not affect the check digit.

> There are totally anti-symmetric quasigroups that detect all phonetic errors associated with the English language (13 ↔ 30, 14 ↔ 40, ..., 19 ↔ 90). The table used in the illustrating example is based on an instance of such kind.

> Despite its desirable properties in typical contexts where similar algorithms are used, the Damm algorithm is largely unknown and scarcely used in practice.

That last point is also why I submitted this :)

[0] http://en.wikipedia.org/wiki/Luhn_algorithm

[1] http://en.wikipedia.org/wiki/Verhoeff_algorithm

Damm

Reply on news.ycombinator.com