Re: Cracking Strings from URLs

Computer Nerd Kev <[email protected]> wrote:
> Rich <[email protected]> wrote:
>> Computer Nerd Kev <[email protected]> wrote:
>>> Computer Nerd Kev <[email protected]> wrote:
>>>> I've got long strings like this from URLs (percent-encoded
>>>> characters have been decoded):
>>>> 
>>>> SdADygkIiM8ED8ZK/ZfkxwbHEgOXnsgKzQcYtq2j3L1HN6OYvET8PwvO2gpCCv4Bp4vIGLwLFN3dDQABOjWT0gVI/EtBlNUIObwLFNnU90IK/gCs2QQzBzhEz8sNAAdBPpmM+T0KRgudx88HxzsFnpjGQs8PBp+fEAvQCgCZnsdKzQz+lpbIBPj7CQ==
>>>> 
>>>> I believe they might be encrypted strings containing one or more
>>>> known fields, probably including a known ten digit number
>>>> (1409518286 in that case). They might also be hashes, but I think
>>>> it's unlikely.
>>> 
>>> I got a copy of the PHP code. Turns out it's a "transposition
>>> cipher" which adds different numbers to the ASCII value of each
>>> character in sequence.
>> 
>> Also called the Ceasar cipher:
>> 
>> https://en.wikipedia.org/wiki/Ceasar_Cipher
> 
> Almost, but unlike the description there, the number of shifted
> positions varies for each character in the encrypted string, since
> the shift length depends on the ASCII value of each character in the
> password. That means you couldn't simply shift the whole string all
> the possible lengths until the string "1409518286" was found in the
> result. Instead you'd have all the possible combinations of
> independently shifted characters = 128 (ASCII character set) to the
> power of the number of characters in the string. In this case
> 128^182 = 3.25e+383, which is ridiculous, but some shortcuts would
> be possible, and probably many more than I can immediately guess.

There was a crank in sci.crypt some years back purporting to have an 
unbreakable cipher that turned out to be a close variant to your 
description above.  His cipher didn't last long once one of the few 
members of sci.crypt who "knew what they were doing" began to attack 
it.

Much later (only a couple years ago now) one of the regulars posted a 
toy algorithm he called SCOS (Sci Crypt Open Secret).  It was intended 
to be a moderate effort one to attack to give folks something to do in 
their spare time.  Quite some number of regulars cracked it in due 
time.  Although the author of the cipher did offer up arbitrary 
encrypted requests (you ask for something to be encrypted, he'd return 
you the encrypted variant) which was helpful in deducing the algorithm.  
It turned out to be a similar "shifting-shift" type cipher as you 
describe.

> 
>>> Very simple,
>> 
>> Yes, that it is, and very weak against attack.
> 
> Probably, but a lot stronger than the Ceasar Cipher by my
> reckoning.

If the above pair on sci.crypt are any indication, it is not much 
stronger than Ceasar.

> Well the brute force approach I had in mind was to try brute
> force using all the different known ciphers in turn, from simplest
> onwards, with this cipher being tried not far after the Ceasar
> Cipher, though very possibly not before some infeasible number of
> possibilities was reached, given the length of the string. That it
> was also base64 encoded would've thrown a spanner in the works, but
> I'm thinking there may also be some smarter general-purpose
> cracking approaches that could be used instead of pure brute-force.
> You don't know if you don't ask...

The successful cracks of SCOS looked for patterns in the output, and 
those patterns provided enough clues to eventually deduce the 
algorithm.

Granted, everyone had more than one ~ 100 character long URL to work 
with, but simply changing the Ceasar rotation with each character isn't 
going to make ceasar a replacement for DES or AES by any measure.  And 
changing it based on the ascii value of the character being encoded 
still leaves behind the underlying frequency components of the 
character usage in the plaintext, which helps to crack the cipher open.