HVM Cipher

[DaymItzJack]

So how did others do it?

I myself converted the HVM to python and brute forced it, after awhile I just guessed the key so save myself some time.

[MyNameIsAlreadyTaken]

I analyzed the Code until I found out, what it is doing - reversing it in C++ wasn't hard after that.


Eventhough afair, it is possible for two distinct messages to be ciphered into the same message - luckily this was no problem in this case.

[laz0r]

I just analysed it, too, reduced it to ((p in base 3) + (k in base 5)) from base 7 to base 10.

[DaymItzJack]

I just analysed it, too, reduced it to ((p in base 3) + (k in base 5)) from base 7 to base 10.

I probably never would have gotten that. At least I know what it is now lol.

[bsguedes]

Executing the code I saw that each plaintext char from the 6th was being crypted by one of the 6 first characters (the key). Thanks to the spaces determining the key was easy. With the key I tried all k-p combinations (6*26) in the HVM and comparing with the ciphertext. Not fair at all, but it was quick

[CodeX]

I just went at it as a simple polyalphabetic cypher with a key length of 6 (based on having a quick poke around with the input/output) and did something like this:

Code: Select all

possibles = __import__('string',('printable',)).printable
KEYLEN = 6
keys = [possibles[:] for i in range(KEYLEN)]

key_mapping = '''
	a dictionary for all the possible keys which returns a
	dictionary of possible outputs, i.e.
		if ctext[i] not in key_mapping['a'].values():
			keys[i % KEYLEN] != 'a'
	this can be used in the end to lookup what cyphertext value
	for the given key to return the plaintext value.

	this dictionary is made by taking every running the cypher
	with a key of all the same characters and a plaintext
	consisting of the printable characters.
'''

ctext = [int(v) for v in "2632 2718 ... 2683 647".split(' ')]

# now reduce the keys
for k in range(KEYLEN):
	key = keys[k] # list of possible keys for every KEYLENth value
	for value in ctext[k::KEYLEN]: # every key + KEYLENth value of the cyphertext
		i = 0
		while i < len(key):
			# remove the value from the list of possible keys if it can't produce a character in the output
			if value not in key_mapping[key[i]].values():
				del key[i]
			else:
				i += 1
	print(key) # will hopefully be a set of length 1 which is the correct key

Which ended up printing out the keys and then I reused the dictionary to reverse the cypher and hey presto there was the answer

[swgr]

I just analyze the code a litttle bit, and the divide the output into groups with 6 number in a group, like this:

2632 2718 2662 2937 557 3026
2968 3003 549 2936 2706 2726
2732 562 2941 2690 2706 2984
569 3005 2710 2937 2713 2738
2963 562 2957 2685 2706 577
2732 2711 2998 529 2718 2985
2976 2711 2941 2683 647

and then, I guess those 500+ are spaces. So I use these information to work out the key.

However I didn't really decrypt the ciphertext when I found that the key is already the answer. I'm to lazy to do the decryption. Can anyone tell me the plaintext?

[dangermouse]

We did it like swgr and bsguedes. We first analyzed the HVM code and found that the ciphertext started at 6, and there was a mod 6 operation to select the key. Additionally, computing the index of coincidence, it was peaking at key length 6 with value 1.73 which is the one for plain English, meaning that the cipher could not be too hard to solve... We encoded space to find the keyword. Then, using test vectors, we found that the plaintext was 'What you seek lies within the key itself!'

[Hippo]

I read the code ... for x starting at 6 till Mx=0:
(Mx base3 to base 10 + key(x%6) base 5 to base 10) base 10 to base 7.

Rest I did manually in excell. (Was easy, and I was lazy to code it).
groups by x%6 ...
... when base 7 to base 10 ends with 0 there must be 0 in key.
... when bases 7 to base 10 differ by 2 minimal value must be in key.

There are twice 2 choices ... but space forces the choice.

[adark]

Necrobump I suppose but I just solved it any I'm happy with my work.

I manually disassembled the HVM and reduced it after some bugfixes (because counting is hard apparently) down to this Lua:

Code: Select all

local memory = {126,664,235,156,145,645,95,96,97,98,99,100,101,102,103,104,0}

function C(x, y, z)
	local v1 = 1
	local v2 = 1
	local v3 = 0

	while v1 < z do
		v1 = v1*x
		v2 = v2*y
	end

	repeat
		z, v1, v2, v3 = z%v1, math.floor(v1/x), math.floor(v2/y), math.floor(z/v1)*v2 + v3
	until v2 == 0

	return v3
end

local i = 6
while true do
	if memory[i + 1] == 0 then
		break
	end
	io.write(C(10, 7, C(3, 10, memory[i + 1]) + C(5, 10, memory[i%6 + 1])), " ")
	i = i + 1
end
print()

I have no idea what the C routine actually does - but I do know that I can calculate it absurdly fast, so I bruteforced it. The value is always increasing as either input increases - so I could bail early, since I didn't want to assume to that anything was in ASCII encoding (turns out it was but, eh, it worked fine.)

I looped through each 'column' of characters encoded using the same key, and compared the valid results, expecting a few possible valid keys for each of the six characters, but it turns out only the second was ambiguous!

From there I just re-bruteforced it using the known key(s) to print out the plaintext.. obviously I already had the answer but this was a fun one to do.

[yes-man]

I just analysed it, too, reduced it to ((p in base 3) + (k in base 5)) from base 7 to base 10.

Yup, that's pretty much what I did. Going through the code and having a good, long stare. Outcome was something like this:

Code: Select all

...
		# main_1
60^<0^2?		# push 6, duplicate, get mem[6], duplicate, jump 2 (to !) if mem[6] was 0 (end of string)
1g!				# end of program or jump over it
355+2v6c		# push 3 & 10; swap current char to top; call stack push; jump back to method_1_INIT
				# that means, calculate the base-3 bit string for the current char
		# main_2
555+			# push 5 & 10 (bases for bit string calculation)
3^0^6/6*-<		# get char index; duplicate; calculate MOD 6 of char index; then get respective key
6c				# jump to method_1_INIT
		# main_3
+				# add base-3 and base-5 bit string together
55+7			# push 10 & 7 (bases for bit string calculation)
2v6c			# switch bit string sum to top; jump to method_1_INIT
...

I liked this challenge. Even better than all the ones where you actually have to write your own code. Also, this gave me some ideas for other challenges ;D