Re: Cracking Strings from URLs

Computer Nerd Kev <[email protected]> wrote:
> 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.

No, not as in "download 'crypto breaker 7.4, now with more breakage' 
and simply plug it in.  They cryptoanalysed the postings.  There was 
some software used for things like computing statistics of the stream 
and the like, but not an "all-in-one" drop in a random base 64 encoded 
url, and it churns and churns and reports an answer.

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

Besides the occasional new crank that drops by with what they believe 
is the "next best thing" the traffic there has dropped to effectively 
zero.  So even if you had posted, there likely wouldn't have been any 
replies.

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

A lot of the technique is/was looking for patterns, then deducing and 
testing hypotheses from those patterns as to what the algorithm was.  
So most of the work was "human intelligence".  The tools were just 
assistants to that intelligence aspect.

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

Is there software somewhere that might crack it?  Maybe.  Will you 
likely find it on github/gitlab/sourceforge, I rather doubt so.  Most 
likely, if such software exists, it is sitting on the disk of whichever 
cryptographer created it for whatever they were attacking at the time, 
and it (the software) has not moved beyond that location.

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

Often web-dev's that "encrypt" URL's like this are doing it either to 
satisfy some checkbox on a requirements sheet from whomever's paying 
their salary, or from a mistaken belief that hiding whatever is inside 
that package from view gives them "extra security".  They would have 
been better off, if they wanted the innards to remain "hidden from 
view" in keeping the innards on their server, and simply creating a 
unique random id that referenced the stored innards.  Then clients have 
nothing to "ecrypt" because the random unique id is merely a pointer 
back to a row in a db table that web browsers don't get to see.