chown

Cipher challenge

17 posts in this topic

I wrote this encryption algorithm in secondary school, in VBScript. My challenge for you today is to crack it :)

It's a classical cipher, meaning no key is involved.

Sample 1:

[r10cs]04X01i01f00 -4M05z-9`05h06q00 -8:-2p07v05|-2l00 07M-8g08€00 00J05z-8e02r-1r00 02Q03y-4a-4n00 06Z02j09n00 -5G04e09ƒ-5t00 -7=09x03j-9%

Sample 2:

[r10cs]04E01q01b-4p-4d05~00 05N06y00 -8L-2f07l00 -2E08t07v-8n08m00 00I05s-8l02q00 -4S02j03l-4_-4d00 06K02x09r07s00 04W09u-5d01q-7l00 03L-9k01t00 -7A05f-4j-8\-4*

Sample 3:

[r10cs]04F01s01v-4p-4a00 -9=05t06x04g-8]00 07I05j-2p08m07m-8l00 -2M00f00 -8O02k-1r-4`02q03p00 -4B06g06r02n09|00 -5O04s00 -5M01v-7b09w00 -9901z00 -7B05y-4o00 -4K-2u-4j00 09`-2c-4e-6a-6b03w-2,

0

Share this post


Link to post
Share on other sites

That's not how cryptanalysis works. Even for a statistical analysis (assuming this is some simple shift/substitute cypher) we would need a page of encrypted text at least.

0

Share this post


Link to post
Share on other sites
What a charming tale of foxes, gloves, and ruin.

Haha, well done :)

0

Share this post


Link to post
Share on other sites

I am not proud to say. but I do not know a goddamn thing about cryptography.

I should start reading.

EDIT: I think I just found some good books on freecomputerbooks.com

Edited by schippystrich
0

Share this post


Link to post
Share on other sites

People can learn a lot from this, great topic chown.

thanks for the info on the books schippystrich.

0

Share this post


Link to post
Share on other sites
People can learn a lot from this

Yeah-> "Don't roll your own crypto: reuse existing primitives, protocols, etc." ;)

0

Share this post


Link to post
Share on other sites

Hold up....

Ciphertext is the encrypted version of the plain text ? Correct

And the Cipher is the cryptographic algorithm? Correct

Can someone give me some basic psuedo-code of how one would go about solving this.

Right now, I am reading about Asymmetric and Symmetric encryption, and One-Way Hashes.

How do you encrypt something without a key?

I am assuming the information to decrypt it is in the ciphertext you gave?

0

Share this post


Link to post
Share on other sites
How do you encrypt something without a key?

You don't. Hashes are not used to encrypt anything, they are used to scramble the original data so that it's impossible to get it back from the resulting hash.

0

Share this post


Link to post
Share on other sites

I know that when it comes to hashes, but in the challenge chown gave us he said no key was needed. WhatChout: Are you saying that he is using a hash function?

If so then how did this come about:

What a charming tale of foxes, gloves, and ruin.

If not then disregard that sentence.

I don't know what a classical cipher is yet, I haven't read enough.

It's a classical cipher, meaning no key is involved.

Anyways it would be really awesome if I could get a break down of how the plaintext was achieved.

Edited by schippystrich
0

Share this post


Link to post
Share on other sites
Hashes are not used to encrypt anything, they are used to scramble the original data so that it's impossible to get it back from the resulting hash.

That's not a fair description of hashing. I could define the worthless hashing function H : {0,1}^* -> {0,1}^n such that H(x) = 0 for all x in {0,1}^* which would fit your criteria (it's impossible to get the input data, since everything just maps to 0!). The idea behind hashing is you take some value 'x' and try to give it a unique value 'y' that takes up less space. By simple counting argument this is impossible, but the goal is to do as best as we can. To wit, a good hashing function H:{0,1}^*->{0,1}^n would have a uniform distribution of mappings from the domain to the range. From a practical standpoint, you'd want for all a, b in {0,1}^n, |Pr[H(x) = a] - Pr[H(x) = b]| is negligible. Additionally, a good cryptographic hash (i.e. a collision resistant hash function) ensures that finding a collision H(x) = H(y), where x != y, is computationally infeasible. There are a couple of "types" of collisions based on how much information you are given, but the most typical is just finding any two distinct x and y that satisfy H(x) = H(y).

If you were to implement a hashing function for a hash table, you would want your hashing function to uniformly distribute its output based on the distribution of your input. While a cryptographic hash would typically satisfy this constraint, it would be overkill.

Anyways it would be really awesome if I could get a break down of how the plaintext was achieved.

First, assume that the plaintext is just ASCII encoded English. Next, note any patterns between the ciphertexts. In this case, there's an obvious header "[r10cs]" and the pattern [-0][0..9][somebyte] consistently repeats (I'll refer to [-0][0..9] as the number field and [somebyte] as the cipher byte field). From the cipher byte field there's some substitution going on since there are a few nonalphanumeric/punctuation characters. Assuming the number field isn't just there for padding, it's likely that it is being used to compute the substitution character. Only a few cipher bytes fall outside of what we'd expect for English and the numbers in the number field are small, so the substitution is probably an addition or a subtraction on a plaintext byte with the number field. Try what's easiest first (e.g. numberfield + cipherbyte and numberfield - cipherbyte) and you'll find you get the plaintext from the latter.

0

Share this post


Link to post
Share on other sites
That's not a fair description of hashing.

I'd argue that it is. What you're presenting is a desired hash function. It has uniform distribution and no collisions. However, to be a hash function, a function simply has to accept input, be deterministic, and produce output that is scrambled so that the original input can never be deduced from the output. Indeed, H(x) = 0 is a hashing function! It has collisions for every input value, but it accepts input, is deterministic and produces scrambled output. SHA-0 has collisions too, but it still is a hashing function.

But I feel like we're going off-topic...

Edited by WhatChout
0

Share this post


Link to post
Share on other sites

Thanks Chz

That is insanely cool, but a bit over my head as of now. In do time.....................

0

Share this post


Link to post
Share on other sites

The conditions "accepts input" and "deterministic" are true of any function in the mathematical sense (however some people choose to abuse the definition of a function so that it can have nondeterminism, but let's ignore that...).

Of course I was talking about what makes a desirable hash function; I said nothing about a definition. Saying hash functions are meant to make data unrecoverable is like saying a dozen tequila shots is meant make you puke all over the mayor. Sure, that's something that it can do, but that's only a useful side-effect of its initial design (i.e. to get you black out drunk).

From a strict sense you can define a hash function as any complete mapping H:X->Y where |X| < |Y|. I assumed you were as well, but it appears you think a hash function is equivalent to a noninvertible mapping, possibly with additional constraints on the set of preimages. While |X| < |Y| is a sufficient condition for a function f:X->Y to be noninvertible, it's certainly not necessary.

You may want a hash function that leaks information about the input. Suppose I wanted a hashtable with two buckets that hold elements keyed by some domain {0, 1, ..., n} (which I would map to the range {0,1}, i.e. the bucket indices). Additionally, suppose I was storing some input stream S(i) (i being the ith key in the stream) where Pr[s(i) = 0] = sum(Pr[s(i) = k], k, 1, n). If I want an even distribution of elements in each bucket, I'd hash H(x) = 0 if x = 0, and H(x) = 1 otherwise, which will result in both buckets containing approximately the same number of elements. However, note that if the domain is small you can deterministically recover the input with a non-negligible probability. Oops!

That was a bit convoluted, but hopefully you can see the utility.

From a cryptographic point of view (managing to vaguely stay on topic), unrecoverability is a consequence of collision resistance. While you can work this out for storing passwords on a server, the threat model tends to get overly complicated; instead, consider a simplified message authentication scenario. Say we had some file with important instructions and its associated hash. The file is distributed through some tamperable channel while the hash is distributed through some public but untamperable channel. To ensure the file is what we expected, the hash on the file is computed and compared against the given hash. If there's a mismatch, it's not the actual file. If the hash is not collision resistant, an attacker could construct a fake file with new important instructions that has the same hash and pass it off as the real thing.

How does this relate back to unrecoverability? Well, suppose a message 'm' can be recovered with non-negilible probability from its hash H(m). This means H(m) reveals some information about 'm' (e.g. maybe if the LSB of m is 0, then the LSB of H(m) is 0). We can use this to our advantage by constructing a message with similar attributes. The lower the entropy, the faster a forged message with a hash collision can be constructed.

0

Share this post


Link to post
Share on other sites
The conditions "accepts input" and "deterministic" are true of any function in the mathematical sense

That's why I included the "scrambles input" part.

Of course I was talking about what makes a desirable hash function; I said nothing about a definition.

Then there must have been some sort of miscommunication between us, for which I'm sorry.

Saying hash functions are meant to make data unrecoverable is like saying a dozen tequila shots is meant make you puke all over the mayor. Sure, that's something that it can do, but that's only a useful side-effect of its initial design (i.e. to get you black out drunk).

That's a bad analogy because puking on people isn't really useful, while making original input unrecoverable is, from the point of security. It's also not so much a side effect as it is another use of the same function.

You may want a hash function that leaks information about the input. Suppose I wanted a hashtable with two buckets that hold elements keyed by some domain {0, 1, ..., n} (which I would map to the range {0,1}, i.e. the bucket indices). Additionally, suppose I was storing some input stream S(i) (i being the ith key in the stream) where Pr[s(i) = 0] = sum(Pr[s(i) = k], k, 1, n). If I want an even distribution of elements in each bucket, I'd hash H(x) = 0 if x = 0, and H(x) = 1 otherwise, which will result in both buckets containing approximately the same number of elements. However, note that if the domain is small you can deterministically recover the input with a non-negligible probability. Oops!

I'd say that's more a result of you not padding the original input to a required length. Sure, the result is small, therefor the input is recoverable, but that would be the case with every hashing function if we used input below certain length, since we're dealing with 2^n possible inputs per given output at worst. (that is, assuming equal domain distribution)

From a cryptographic point of view (managing to vaguely stay on topic), unrecoverability is a consequence of collision resistance.

I'd disagree. F(x) = x + 1 is resistant to collisions for all x in R, yet it is recoverable. The key is both collision resistance and infeasibility of inversion of resulting output.

0

Share this post


Link to post
Share on other sites
I'd say that's more a result of you not padding the original input to a required length. Sure, the result is small, therefor the input is recoverable, but that would be the case with every hashing function if we used input below certain length, since we're dealing with 2^n possible inputs per given output at worst. (that is, assuming equal domain distribution)

What do you mean by padding the original input? From an information standpoint it's exactly the same. I was just saying that you may want a hash function that reveals information about the input. Perfect hashes fall in this category too.

F(x) = x + 1 is resistant to collisions for all x in R, yet it is recoverable. The key is both collision resistance and infeasibility of inversion of resulting output.

That's not a hash function because the size of your domain is the same as your range (I'm assuming F:R->R here). Collision resistance only makes sense when you have collisions. I'm fairly certain that a hash function that is collision resistant is also strong against a hash inversion attack like you describe (i.e. you are given H(x) and want to find some x' (which is not necessarily distinct from x) that satisfies H(x) = H(x')). The proof would involve assuming you had an algorithm for finding collisions that did better than what you could achieve via the birthday paradox, show there is a bias, then base your inversion around that bias. I said something similar to this at the end of my last post. On the other hand, resistance against hash inversion definitely does not imply collision resistance.

The type of function where you can invert the input that has the properties you're interested in would likely be a pseudo-random permutation. In fact, there's a common construction for cryptographic hashes that uses PRPs.

0

Share this post


Link to post
Share on other sites
What do you mean by padding the original input?

Most hashing functions require the size of the input to be a multiple of a certain number, so if it's too short or too long, it gets ones or zeroes appended to be of the required size (or multiple of).

The type of function where you can invert the input that has the properties you're interested in would likely be a pseudo-random permutation. In fact, there's a common construction for cryptographic hashes that uses PRPs.

Thanks, I didn't know that.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now