[Challenge] Password Protected Program

Does your 3DS not work? I'm not sure how much progress you could make from just looking at the source code if you can't run it. Here's a link to the source code. The program is very sensitive to changes, so if you copy it to your 3DS and it doesn't run then make sure it's exactly 5414 bytes long and is named "LOCKED".

I errr never really had SmileBASIC or 3DS. I came over from PTC and accidentally got attached doing work on the site and now I'm just a sort of tumor. I can emulate SB, though, and this looked interesting, which is why I though I'd ask for the file. Thank you!

How are you emulating it? On a 3DS emulator? I don't know how any platform but the 3DS works with SmileBASIC so the program is designed specifically for SmileBASIC on 3DS. I have no clue how it'd hold up or if it'd run at all on other platforms.

With citra, yes. I had no problems with getting it to run. One thing you may have neglected to prevent is peeking at variables after execution, which can be perhaps be used to deduce the result of the password hashing and the contents of the label table... Anyway, it's put together well and I'll keep looking at it when I get home, assuming someone else hasn't cracked it by then.

Yeah, I did notice that but I wasn't sure how to prevent. The program is designed so that any discrepancies between the original code and the currently running code causes it to crash, and when a program crashes all its variables are still viewable. It's sort of inevitable with the current method I'm using, I'll have to come up with a different method entirely to prevent that.

Right, I guess I didn't realize the table would be constructed before a crash trying to use it. Still, you can prevent variables from being read after normal execution [by clearing them]. I just assumed the normal flow would be the most useful to read, but this could be a bad assumption.

Ooh this is very good wow. may have to spend some time on this.

There's no red herrings. Everything in the program is there for a purpose.

inb4 actual poster answer

Spoiler

It's "part of the challenge" in the sense that they are the apparent part of it. Whether you need to do anything with them is not necessarily the case. But, they are used by the program; it isn't a herring or anything.

Edit: poster is fast. could not obtain in before. Will delete if requested.

brute force attack on password reported a success... that contained a non-printing character. Oops.

type (1)

Spoiler

Unfortunately, it took 2 hours after <above comment> to learn that you can in fact recall prompt history from INPUT. Since that I've found a series of passwords that are much easier to type.

Have some thoughts on (2) that I want to try.

So you bruteforced it? The hashing algorithm I used likely isn't very secure because, well, I just came up with it off the top of my head, so I'm sure there's a lot of collisions and several potential passwords that will actually work. If I have the free time I've considered bringing something like Blake2 to SmileBASIC which should solve that.

Right. There wasn't anything preventing me from copying the hashing code, replacing the table lookups with the absolute values from the method suggested above, and then throwing random values at it inside smilebasic. I did try to port it but I guess I did it wrong (or it abuses some SB arithmetic features that I didn't account for), I think I only produced the correct hash with single-character keys or something. I don't know much about cryptography, so I can't really analyze it, but in the key I came up with the fourth character could be replaced by several multiples of 8 (Chr$(64), Chr$(88), Chr$(96), Chr$(128), ...) and still work, which was a little amusing. Resorting to a... "black box" crack like this would still be a success on your side, but I did have to de-obfuscate the program to find the relevant parts... some of the jumps are even guessable, though e.g. @1510RETURN help confuse that. Since the values in the table are sequential based on location in the program, they could probably still all be deduced with a little patience (I opted for the easier method). Reversing the hash... probably not an option, and still not really the problem. Considering that the working part of the program can be lifted out once the table is known, I'd consider being able to perform basic de-obfuscation and obtaining the table as a partial success for programs of this type. Please correct me if I'm neglecting something. I'll still see what I can do about (2).

Hashing algorithms are one-way functions and the algorithm is intended to be public as they can't actually be reversed. The issue is that with poor hashing algorithms, they have a lot of collisions, this means that a lot of possible inputs would yield the same output, making bruteforcing it not take a considerable amount of time. Again in the future I'll consider porting a serious hashing algorithm to SmileBASIC, something more cryptographically secure with much less collisions.

Example identically functioning program, freed from the tamper-protection mechanism: https://pastebin.com/raw/hqU8pbZD The time it would take to free a program protected this way really just depends on the time it takes to replace all the label references. The faulty assumption in the program is that it cannot function without generating the table, which depends on the integrity of the program. However, all it really needs is the table at all. Thoughts on preventing this... umm, I didn't look too closely at @0004-@000A, but you could do a quick integrity check beforehand and abort--or better, fill the table with garbage--to prevent the [edit, crash, peek] situation [1]. It also might be good to encrypt the values in the table... if the decryption code is scattered everywhere (you already have the means to scramble the program in this way), it would be a lot harder to crack the table, maybe... oh, but I guess then the decryption can't rely on the table, oops.[2] [1] EDIT: as well as clearing the table after normal runs [2] EDIT: Of course, any of that just makes the table harder to crack, it doesn't necessarily fix "can't be taken out of original context"

The issue with doing a quick integrity check is that if you've already replaced all the labels, you could just delete the integrity check code. And encrypting the table would require on-the-fly decryption which would introduce a ton of overhead in the program. The core idea to this software is to calculate values during "lock time" (when the program is ran through the "locker" program) and then modify the code to incorporate those same values into the program at run time. The issue is that you can never simply do checks between these two values because it would introduce too much overhead, instead you need to find a way to rearrange the logic in the program to rely on those values to function. The label method's probably not the best method because you can substitute in the table once you figure it out, I'll need to look into other methods... the annoying part is that I can't find any resources on anyone else trying to make similar software, so it's purely up to me to come up with these algorithms myself.

Mmm, I forgot that there are plenty of chances to halt the program while it has the table. That would break the prior check. There was an on-the-fly chunk decryption-encryption of program data method that I thought would be interesting to implement in SmileBASIC. I'll see if I can find the paper, but you mentioned overhead, so maybe even that won't be feasible.

I believe this is the one I had seen.

Multi-blocking encryption breaks up a binary pro- gram into individual encrypted blocks. The program is executed by decrypting and jumping to the executable block during the run-time process. When not being executed, blocks are in encrypted form

"Cipher block chaining" seemed like a similar idea, with encrypted blocks that are individually decrypted, used, then encrypted again and the plaintext is used as the key for the next block, or something like that. I don't really know if it would work in SmileBASIC, nor could I implement it myself, but maybe it'll be helpful.