Re: Cracking Strings from URLs

Rich <[email protected]> wrote:
> 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.

I take it they didn't attack it by automated means using free
published software though? Which is all I'm really after. Like I
said, I can imagine ways one could code one's own optimised
software routines to help crack it, and I'm sure there are better
ones than I can immediately think of. But I don't get much fun out
of that myself and am only really interested if someone's published
their existing work in an easy-to-use form. Like the various free
password hash cracking tools for Linux.

> 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.

I looked in sci.crypt before posting but wasn't sure whether asking
about available cracking software was on topic or not. It seems
this thread is drifting away from that now anyway. The academic
aspects of cryptography are of limited interest to me beyond their
immediate pracical use to perform a real-world task. But I guess
if people are posting such challenges there, it does suggest that
most sci.crypt regulars don't know of free software to break them,
or else there might not be much point.

>>>> 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.

The techniques to crack it efficiently must be significantly more
complex than the obvious brute-force approach to craching the
Ceasar Cipher.

>> 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.

I was never proposing to use this method to encrypt things myself,
especially before I even knew what it was! My (correct, according
to you) assumption was that it _would_ likely be weaker than modern
encryption schemes, and therefore theoretically crackable. My
question was whether software was available to test that theory by
using known techniques to try and crack it, given I knew part of
the correct decoded output.

> 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.

Well not so much in this case since the content was mainly numbers
and random alpha-numeric strings, no words except for a domain name
and directory in a URL (in fact a pretty silly thing to encrypt).
That makes a practical technique to cracking it harder than what I
can immediately guess, but I suspected there would be cracking
techniques in use that are far more sophisticated than I can
imagine. Techniques possibly already implemented in free software,
but it seems maybe not.

-- 
__          __
#_ < |\| |< _#