Securely map random string to a custom charset

Question

I'm writing a Python script to generate custom passwords based on a HMAC. I want the passwords to support various websites requirements so I want to map the HMAC output (ex: hex format) to an array of allowed characters.

Let's say I want to map 'fea503e5' to numbers only.

The issue is doing it securely, as using modulo :

# numbers = "0123456789"
# pwd = ""
# ascii_digest is [65, 66, 67] for string "abc"
for i in ascii_digest:
    pwd = pwd + numbers[i % len(chars)]

is not secure because some letters have more chance to be picked (multiples of 10).

Will the tr program do this securely ? Also how does it work or more so, how a safe mapping function is to be implemented ?

possible duplicate of [Is the following password-generator secure?](http://security.stackexchange.com/questions/41501/is-the-following-password-generator-secure) — RoraΖ, Oct 08 '14 at 15:21

score 1 · Accepted Answer · answered Oct 08 '14 at 16:47

You can [65, 66, 67] convert to 656667. Since you can recompute it back, it would be of same security level. However, I suppose this is not what you really want. I guess, you want the result with as little letters/digits as possible.

Consider the password as a n-base number where n is number of possible characters in the password. What you really want is to convert n-base number (password) to m-base number where m is number of character in the destination set. It's easy if you have just small numbers which can be held in the integer value. It's more difficult with larger numbers however, you would need just a middle school arithmetic.

For example, we have 26 letters a..z. bcd = [1, 2, 3] would be 26-base number (letter a is 0). You can convert it to integer easily:

n = 1 + 26 * 2 + 26^2 *3

BASE = 26
res = 0
k = 1
for n in abc:
    res += n*k
    k *= BASE
return res

It's like 1234 = 1 * 10^3 + 2 * 10^2 + 3 * 10^1 + 4 ^ 10^0 just 10 would be 26 :-)

Then, you can convert it to 10-base (or whatever base) number:

BASE = 10
while(n):
   out.append(n % BASE)
   n=n/BASE
return n

As I mentioned, the problem could be a large number. You can implement it by yourself and it's not as difficult as it looks, just use the base division algorithm which you learned on your middle school or even earlier, or you can try to find some big-number python library which would be even easier.

The clarification of my problem into a n-base translation was exactly what I needed to grasp this and more over doing it nicely. For the record, what I did then was to take each remainder (n%BASE) as an index for a string containing the alphabet to complete the translation. Thank you ! — Irving Poe, Oct 08 '14 at 21:38
just keep in mind 32bit integer number would hold just more or less 8 letters password then it overflows. You'll have to implement your own division/modulo/multiplication, represent the number as array. It's not difficult, I used to implemented it as a school project in assembler on x86 when I was 15. — smrt28, Oct 09 '14 at 10:43
Yah, it does. I didn't know long is so long in python :-). Thanks — smrt28, Oct 09 '14 at 12:07

Securely map random string to a custom charset

1 Answers1