# Reversing an encoded key with a given cipher - figuring out the reverse algorithm

So I have an ancient application for a company that has since gone bust and I thought I'd look at how it works; it provides a key, and requires a key given to it. Both these keys are encoded in a certain way and then parts of the encoded value are compared for equality. Firstly I'll explain the encoding process as I have remade it in javascript

This appears to be a caesar cipher in some shape or form and I'm pretty sure it equates to the formula: `C(x) = (P(b - a - x + 284) mod 26) + 48` where
x = character number
b = current characters index in alphabet
a = previous letters index in alphabet

``````const alphabet = `SDHACENOIFKXQLBMPJTZURWVGY`

function encodeString(s) {
var result = s.charAt(0),
lastLetterIdx = alphabet.indexOf(s.charAt(0))

for(let i = 0; i < s.length - 1; i++) {
let thisLetterIdx = alphabet.indexOf(s.charAt(i + 1))
let cypherNum = thisLetterIdx - lastLetterIdx - i
cypherNum += 284
let modNum = cypherNum % 26
let encChar = String.fromCharCode(modNum + 48)

result += encChar

lastLetterIdx = thisLetterIdx
}

return result
}
``````

A key provided by the software is
`ALVMGRCTQQEYMNAHDANKPGKPO`
which gets encoded to
`A87>4A26;@8833898:::;<?8B`

The code is then checksumed by skipping the first character and adding the ascii values up, so in this case that number is 1378, mod 25 = 3 and the alphabet character at position 3 (0 indexed) is `A` which matches the first character of the key.

For encoding step 2 the software takes characters 1-12 (87>4A26;@883) and encodes it into a number via the following:

``````function encodedStringToNumber(str) {
var number = 0,
letterMulti = 1
for(let i = str.length; i > 0; i--) {
if(i < str.length)
letterMulti = letterMulti * 19

let letter = str.charCodeAt(i-1)
letter -= 48
letter *= letterMulti

number += letter
}
return number
}
``````

It then converts the number to a string and pads left with `0` to ensure its 15 characters long, after doing that with both half's it string concats the numbers to get a result of
`979440403325666401568800000018`

If we do the same thing with a random test key I made of `VABCDEFGHIJKLMNOPQRSTUVWXYZABK`
we get an encrypted key of
`V48<BHG7EFH7@>2;B4@;G661@>C88B`
that gets checksumd as before and then gets converted to a string with 11 characters from index 1, 11 characters from index 12 and 7 characters from index 23, so:

``````48<BHG7EFH7
@>2;B4@;G66
1@>C88B
``````

We convert them to numbers then ensure string lengths of 14, 14 and 7 by padding the left with `0` again. So a result of
`2732684617734210265934650819588621338`

We now split this number and the number provided in the software down to some key elements and compare the values.

Lets say key A is the software provided key of `979440403325666401568800000018` and key B is the key I'm randomly using of `2732684617734210265934650819588621338`

From key A take characters (indexes are 1 based here):

``````3-4   (94)
28-29 (01)
6-7   (04)
8-9   (03)
10-15 (325666)
5     (4)
17-22 (015688)
``````

From key B take:

``````3-4   (32)
1-2   (27)
29-30 (58)
15-16 (10)
31-36 (862133)
28    (9)
17-22 (265934)
``````

Those values need to be the same and as an added check key B 6-8 needs to be "999" (i think this is an install flag and 000 is an uninstall flag)

So with the key given by application I know I need to make a key that encrypts to the following number (where X can be anything):
`0194x999xxxxxx03015688xxxxx404325666x`

This number needs to satisfy the comparisons, have the 999 in the correct place and when encoded as letters needs to validate the checksum mentioned earlier along with each letter of the encoded value being >= '0', by that I mean the ascii value is at or above 48.

The problem I have is given the way it encrypts the key I can't for the life of me work out how they could make a program which does the reverse, the first step seems easy if I knew how to do modular arithmetic, but converting a number to letters is straight up beyond me.

• Make your own rainbow table and hope you hit something. Jan 25, 2020 at 16:41
• @JohnGreene I actually tried that approach but its surprisingly not a fast approach. but I'm more curious how a generator would work Jan 25, 2020 at 17:18
• encodedStringToNumber("@>2;B4@;G66") = 102659346508195, which is 15 characters long, not 14. Am I missing something? Jan 25, 2020 at 18:55
• Also, there's a missing index in "31-35 (862133)" and you should probably explicitly state that the indexes are 1-based. Jan 25, 2020 at 19:14
• You might be able to use Z3 in order to find an appropriate input. Basically you need to translate your constraints using the Z3 syntax. You can search for "Z3 KeyGen / CrackMe" for some examples. I gave it a shot but I'm not sure how to express some constraints, you can find my attempt here if it helps: pastebin.com/hdbhTkRy Jan 26, 2020 at 18:04

I'm write keygen random: `keygen('ALVMGRCTQQEYMNAHDANKPGKPO')`

``````GSFLOWZJOEWPOQFXFHVASFTPNBNTEJ      ->      G060?9@@7>684A8<712<2=<0A8A::8

060?9@@7>68           4A8<712<2=<            0A8A::8
01949999431597        030156882999840        43256662 (length 14 + 15 + 8 = 37)
``````

0194999943159703015688299984043256662 this satisfy with 0194x999xxxxxx03015688xxxxx404325666x :D

``````// example
keygen('ALVMGRCTQQEYMNAHDANKPGKPO')
// source
function keygen(code) {
let indexes = [
[3, 4, 28, 29,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15,  5, 17, 18, 19, 20, 21, 22],
[3, 4,  1,  2, 29, 30, 15, 16, 31, 32, 33, 34, 35, 36, 28, 17, 18, 19, 20, 21, 22]
]
code = encodeString(code)
let key = [...Array(37)].map((e,i)=>[5,6,7].indexOf(i) >= 0 ? '9' : Math.floor(Math.random()*10).toString())
indexes[0].forEach((e,i)=>key[indexes[1][i]-1]=num[e-1]), key = key.join('')

return decodeString(sum(result,0)+result)
}

var alphabet = `SDHACENOIFKXQLBMPJTZURWVGY`
function encodeString(s) {
let result = s.charAt(0), idx = alphabet.indexOf(s.charAt(0))
for (let i=0; i<s.length-1; i++) {
result += String.fromCharCode((alphabet.indexOf(s.charAt(i + 1))-idx-i+284)%26+48)
idx = alphabet.indexOf(s.charAt(i + 1))
}
return result
}
function decodeString(s) {
let result = s.charAt(0), idx = alphabet.indexOf(s.charAt(0))
for (let i=0; i<s.length-1; i++) {
let num = (s.charCodeAt(i + 1) - 48)
idx = [...alphabet].findIndex((x,y) => (y-idx-i+284)%26 == num)
result += alphabet[idx]
}
return result
}
function encodeNumber(s) {
let n = 0, l = 1
for (let i=s.length; i>0; i--) {
let c = (s.charCodeAt(i-1)-48)*l
n += c, l *= 19
}
return n
}
function decodeNumber(n) {
let c = 0, s = []
for (let i=0; c != n; i++) {
let v = (n % 19**(i+1))
s.push((v-c)/19**i+48)
c = v
}
return String.fromCharCode.apply(null, s.reverse())
}
function sum(s, idx = 1) {
let cs = 0
for (; idx < s.length; idx++) cs+=s.charCodeAt(idx)
return alphabet[cs%25]
}
``````
• Oh my! That's an ingenious way to do it. I was trying out the number to string conversion and got something working but I was doing trial and error on the string conversion, this really has opened my eyes lol. It works btw! gonna be debugging this for a while Jan 27, 2020 at 21:25