1

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. – John Greene Jan 25 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 – Julian Jan 25 at 17:18
  • encodedStringToNumber("@>2;B4@;G66") = 102659346508195, which is 15 characters long, not 14. Am I missing something? – Dvd848 Jan 25 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. – Dvd848 Jan 25 at 19:14
  • 1
    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 – Dvd848 Jan 26 at 18:04
1

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

run

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 num = encodeNumber(code.substr(1, 12)).toString().padStart(15,0)+encodeNumber(code.substr(13, 12)).toString().padStart(15,0)
 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('')

 let result = decodeNumber(key.substr(0, 14)).padStart(11,0)+decodeNumber(key.substr(14, 15)).padStart(11,0)+decodeNumber(key.substr(29, 8)).padStart(7,0)
 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]
}
| improve this answer | |
  • 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 – Julian Jan 27 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.