Well, since we're talking about 16 bit software ...
In 1991, my company was sandboxing commercial software. This was for try-before-you-buy. Except, instead of recompiling a crippled version, we would take a retail SKU, encipher the executables and then deliver with a device driver: a VxD. The VxD would hook the low level Int13 IO calls to pass all disk IO through a write-through cache. The installed app could read from anywhere on the disk. But, all attempts to write would copy the changed sectors to the cache. This would allow a perfect uninstall; simply remove the cache and the disk reverts back to its preinstalled state. This was because most software, back in 1991, assumed that you'd never want to uninstall. So, it would scatter its junk all over the place.
Now imagine if the VxD was part of the OS. Any downloaded exe could access the HD, but all writes would write-through to a separate cache. That was 25 years ago. This is a roundabout way of asking: how feasible is sandboxing to avoid malware?
Windows Embedded has the Enhanced Write Filter can be enabled to redirect all writes to a disk to memory. You optionally use an admin tool to commit changes on a clean reboot. Many years ago one of our embedded PCs got Conficker from a Service techs laptop. Rebooting the machine was enough to restore it to clean state since nothing was written to disk. Not a solution for everyone but its somewhat similar.
The Linux machines in MIT's computer labs do essentially the same thing. Right after you log in, there's a wrapper around your entire X session that union-mounts a tmpfs on top of the root filesystem, puts you in that chroot, and gives you root. It's not secure against active malice (and not intended to be, since you have physical access to the machine), but it lets people run `sudo pip install` or `sudo npm install -g` or `sudo make install` or whatever, and it only stays around until they log out.
The trouble with root access is that there's always a way for active malice to get in. For instance, our approach is trivially vulnerable to loading a kernel module. It's possible that something like user namespaces would solve that today.
Are you sure it's not even more trivially vulnerable than that? From man 2 chroot:
This call does not change the current working directory, so that after the call '.' can be outside the tree rooted at '/'. In particular, the superuser can escape from a "chroot jail" by doing:
There are a handful of other vulnerabilities, yes. That one will likely work.
However, there are some kernel patches floating around that disable double-chroot, so just as such an attack would be easy, blocking that specific attack would be easy too. My point was that there are lots of things that root can do, and blocking them all is difficult; in general root is trusted to load drivers, which means it can bypass any driver that confines it. There's no direct equivalent of chroot on 16-bit DOS/Windows, but you could almost certainly bypass OP's filtering scheme by loading your own VxD that fought with theirs.
you have misunderstood what you are reading. man 2 is the library doc not the chroot program, this page is just reminding people to cd into the root otherwise they will be vulnerable.
You're right insofar as you can't use the chroot command to escape a "chroot jail" because it automatically calls chdir() for you, but any root user can escape one by invoking the following linux system calls:
chdir("/"); /* go to / of "chroot jail" */
mkdir("foo", ...); /* create directory in jail */
chroot("foo"); /* change / to foo */
/* fail to chdir("foo"); */
chdir(".."); /* instead go up parent (there is nothing preventing you since you are no longer in the "chroot jail" since the jail is now foo and you never entered it) */
chdir("..");
/* ... */
chdir(".."); /* . is now the real root */
chroot("."); /* change / to the real root */
This is why the man pages for the linux system call rightfully put "chroot jail" in scare quotes. They are trivially escaped by a root user making basic linux system calls, and the man pages even sketch out how for you. Some operating systems attempt to provide more secure chroot jails, but linux chroot() does not provide this.
No, parent's understanding is correct. You're thinking of a different (and also valid) attack. Both attacks rely on the fact that the chroot system call remaps the chroot's parent directory to itself (so you can't "cd /; cd .."), but if you are anywhere else, whether inside or outside, no such remapping is performed.
Parent's attack requires the attacker to have root inside the chroot. It's a "double-chroot" attack: you call chroot a second time as root, so a new directory starts getting remapped. Then the old one no longer does, and you can "cd .." out of it and eventually "chroot ." when you get to the top. The only mitigation is not to give an attacker root inside a chroot.
Your attack does not require the attacker to have root. Instead, the process who was setting up the chroot (which does have root) forgets to cd into the chroot, and leaves the working directory outside it. The attacker cannot chroot again, but they can continue to cd anywhere on your filesystem.
Aha, looks like SteadyState accomplishes the same thing. Very cool! I wonder how a Windows Restore Point is defeated? Because it is in the same partition?
Malware can disable System Restore and delete existing restore points if the user account they are running under has the rights to do so. I think the Cryptolocker variants did this, but not sure...
Maybe I am too old school, but I can't understand how all these fancy 'constraint solvers' (and in another solution, definitions akin to genes and chromosomes (hair raising) https://news.ycombinator.com/item?id=11474613) are helping to write a standard brute-forcer for the flawed algorithm? Are these solvers doing anything more intelligent??
Solvers don't do brute force at all. Otherwise you wouldn't come up with ways to crack crypto. Solvers work with SAT and SMT languages, which means purely logical and extended to simple words and bitarrays, and the solvers mentioned there (cbmc is also in this league), can solve normal programming logic backwards.
Means you assert a result on a variable at the end, specify which variables and states will affect the wanted result, and the framework and solver will efficiently backtrack all the possible solutions of input variables to come up to your desired endstate, by filtering out impossible paths and values. Like in a game.
Z3 is very popular, because you can write your problem in python.
Ages ago lisp was very popular, and some of the very first lisp programs from the 60ies were such solvers (general planner) leading to AI.
And recently with the implementation of efficient simple open-source SMT solvers (minisat, ...) implemented within gcc or llvm you can now even use normal C programs and backtrack results, optimize and check types, do bounds checking, generate tests from bugs and so on. This is not comparable to simple fuzzing or brute-forcing, it knows the program flow, and works the flow backwards.
Thanks for explaining! I just can't understand how such 'solvers' can help with crypto, when strong crypto-algos are not reversible and hence there is no point to approach them backwards?
If any algorithm can be weakened by such 'problem solvers', it wouldn't be considered strong? For instance, can SHA256 be reversed (i.e. collision found) faster with such a solver? I guess not..
I realize that with crypto, solvers can optimize the flow of the algorithm, make it more efficient and omit repeating some code parts, but a good bruteforcer written in assembly can be as optimized..?
SAT solvers can solve logical problems much faster than brute force. They take advantage of heuristics, and they use certain mathematical techniques to rule out parts of the search space and narrow it down significantly.
In general most crypto can't be broken by solvers. The solvers might be faster than brute force, but still take exponential amounts of time to solve it. However if the crypto was designed badly, there can be weaknesses in it that the solvers can find and exploit.
It's basically like those logic puzzles that are sometimes asked to kids. I don't have a specific example handy, but they go like "Fred won't sit next to Bill. Bill wants to sit next to Mary. Mary wants to sit in the same table as Ned..." And then they ask you to find a seating arrangement that satisfies all these constraints.
You can try every possibility, and there are exponentially many as you add more people. But if you are clever, you can realize certain constraints rule out large portions of the search space. Like you know the answer must have Mary in the same table as Ned, so you don't even try any possibilities where that's not true. There are many other clever tricks SAT solvers use to shrink the search space.
Crypto algorithms are deterministic, and therefore reversible. Solvers would work with any crypto, it's just that with normal crypto your computer would degrade to dust before they had time to finish. This was breakable because the Salsa algorithm was processing 16 bits instead of 32, which makes the set of possible earlier states astronomically smaller.
A "properly" implemented 16 bit Salsa20 would have 64/128 bits of key, which would still take a very long time to break. The reason _this_ implementation was broken (assuming the referenced snippet [1] is accurate) is the rotl function and the rotation values. The shifts are being calculated for 32 bits but are being used with 16 bit values. Instead of all 16 bits being rotated and used, half the shifts result in 0 while the others affect only a handful of high bits, which means there is very little diffusion going on.
I think the misunderstanding is just definitional, if you're searching on a constrained-space it wouldn't be called brute-force, though by all means you are still enumerating possible solutions.
> Brute force search should not be confused with backtracking, where large sets of solutions can be discarded without being explicitly enumerated *
> solver will efficiently backtrack all the possible solutions of input variables to come up to your desired endstate, by filtering out impossible paths and values
That seems to be a contradiction, because Back-Tracking uses Brute-Force. The efficiency comes from heuristics that can fail, which is kind of important to note. SAT problems are in principle np-complete with all the uncertainty that implies.
>And recently with the implementation of efficient simple open-source SMT solvers (minisat, ...) implemented within gcc or llvm you can now even use normal C programs and backtrack results, optimize and check types, do bounds checking, generate tests from bugs and so on.
coq: https://coq.inria.fr/a-short-introduction-to-coq
the real beast out there. easy to install. but hardly usable for normal hackers, because of their mathematical notation.
but it's using plain c, and you can verify c with various solvers.
for crypto https://srlabs.de/minisat-intro/ has some explanation how to break weak ciphers or hashes, knowing the weakness beforehand. but the various hackers posting on their blogs usually have better practical explanations.
Searching for "expand 32-byte k" would directly lead you to Salsa. The exact code used in the malware can be found here. I am using the word exact in a broad sense. If it had been a ditto copy, we would have no chance of breaking it. The original Salsa implementation uses 32 bit (uint32_t) variables. This salsa implementation uses 16 bit variables for the same purpose borking it badly.
:)
The author made it look so easy to reverse this. Kudos, and thanks for the community service.
Yes, but that's not explicitly mentioned in the article and is expected given that it's targeting a specific platform. You could say the same of OSX.
fwiw I've been using various flavors of linux for years(CentOS/Arch/FreeBSD lately) for everything but a single dev laptop I keep Windows for testing/native apps.
My comment wasn't meant to be advocating Windows, let alone XP, I just thought it was funny.
This is not bruteforce.
The flaw is the attackers used the same crypto algorithm but with smaller width variables. This rendered some of the crypto useless. Half of the total bytes in the keystream are always null and correspondingly half of total bytes in the ciphertext retain their original value. always
Even with 16-bit variables proper implementation would have made this a lot tougher.
I have a feeling the malware author, working in 16-bit realmode, forgot that ints are usually 16 bits wide in that environment. A "typedef unsigned int uint32_t" behaves as expected in the usual 32/64-bit environment, but not in 16-bit. It's unlikely the author invented the 16-bit Salsa20 variant, but rather copied existing code and just compiled it wrongly.
I find it extremely amusing that after going through all the trouble of building the malware+infrastructure to sell keys, the authors couldn't be troubled to write the 5 lines of assembly code to enter protected mode. You can even leave paging off!
You don't even need to be in protected mode to use 32-bit registers. You can sort of bounce in and out just enough to use them with the 66 prefix. I used to do that but it's been so long I forgot how.
That's right, I was, but on further reflection you don't need to do anything special in this case since it's just doing 32 bit math, not 32 bit addressing. EAX/EBX/etc should just work in real mode IIRC.
Regarding the 'expand 32-byte k' part: I've seen other malware that obfuscates its strings that way, by writing them into a buffer using one instruction per character, so you can't retrieve them with a simple 'strings' command. The thing that bugs me is they've gone to that length to hide the string, but they didn't randomize the order of the instructions, and as a result you can trivially retrieve the string with your disassembler.
In 1991, my company was sandboxing commercial software. This was for try-before-you-buy. Except, instead of recompiling a crippled version, we would take a retail SKU, encipher the executables and then deliver with a device driver: a VxD. The VxD would hook the low level Int13 IO calls to pass all disk IO through a write-through cache. The installed app could read from anywhere on the disk. But, all attempts to write would copy the changed sectors to the cache. This would allow a perfect uninstall; simply remove the cache and the disk reverts back to its preinstalled state. This was because most software, back in 1991, assumed that you'd never want to uninstall. So, it would scatter its junk all over the place.
Now imagine if the VxD was part of the OS. Any downloaded exe could access the HD, but all writes would write-through to a separate cache. That was 25 years ago. This is a roundabout way of asking: how feasible is sandboxing to avoid malware?