10 ms·

Say a trusting trust attack is discovered. Whats the resolution? Do you manually edit the binary? Do you rewrite a compiler in a language with a verified compil

Say a trusting trust attack is discovered. Whats the resolution? Do you manually edit the binary? Do you rewrite a compiler in a language with a verified compiler? Would something like randomizing memory layouts, or reversing stack direction be an easy mitigation or solve an attack like this?

rusbus 10y ago
Randomizing memory layouts and modifying the stack will have no impact since this attack isn't exploiting anything in the language, you've created a compiler that intentionally miscompiles source code. And not only does it miscompile source code, it miscompiles itself so that it preserves the exploit. One potential way to try to remove attacks like this is to run the source code of the compiler through something that randomizes the structure and text without changing how it actually functions. That way, you may be able to defeat the code that is trying to match on code that looks like the part of the compiler it's trying to hijack.
logicallee 10y ago
you use an old compiler binary that didn't have the attack yet to compile the latest source code that it is able to compile, then use that compile the latest it can compile, and so forth. what I mean is that I wouldn't expect a the 2012 rust prerelease to be able to compile the 2016 rust source code, but it can probably do 2013, use that to compile 2014, use that to compile 2015 use that to compile 2016. As long as you have a single binary from any point before the attack was introduced it shouldn't be an issue. The whole point is that at no point does the source code contain the trust backdoor, so you can just work forward from any binary that doesn't have it yet. if the very first version of rust binary already had it as an issue, as well as was written in rust, you could conceivably have a problem though. then you would need an alternative compiler, however sub-optimal it might be... or you could simply patch and remove the backdoor from the binary and then have it compile itself without inserting the backdoor.
- Manishearth 10y ago
  > but it can probably do 2013, use that to compile 2014, use that to compile 2015 use that to compile 2016. Clearly you aren't aware of Rust's history :) proto-Rust has been under so many rapid changes that each compiler usually only compiles with a specific hash. Now stuff works with a numbered Rust release, but that's a relatively new phenomenon. This process will likely need to go through hundreds of compilation steps. Doable, but not as simple as a year-by-year process.
  - vog 10y ago
    I believe the year numbers were used by logicallee only as an example. Of course, if somebody is trying this, they need to figure out a different (smaller) time scale that actually works. In the worst case, you have to follow each commit in the version control system of the compiler, but I'm pretty sure you don't need to do it that fine grained.
    - logicallee 10y ago
      yes. I'm pretty shocked Manishearth didn't get that I was just giving examples of the process with placeholder dates, since I started my comment explicitly stating (I add emphasis here): >you use an old compiler binary that didn't have the attack yet to compile the latest source code that it is able to compile, then use that to compile the latest it can compile, and so forth. in trying to find the "latest source code that it is able to compile" you can do a binary search backward from the current version of the source code. it doesn't take long to find the latest version for each one (i.e. the latest each one compiles without error, into a working binary that passes some test suite). And anyway whenever you're binary-searching forward (i.e. after any point where the binary search yields ""greater-than" because the one you just tried compiled) then you can just use the version you just successfully compiled. Let me illustrate what i mean with this binary search: so if we're at version 1 million today, which the version 7 doesn't compile, then you try version 7 on version 500,000 (it'll fail), then on version 250,000 (it'll fail), version 125,000 (it'll fail), version 125,000 (it'll fail), version 62,500 (it'll fail), version 31,250 (it'll fail), version 62500 (fail), version 31250 (fail), versions, 15625, 7812, 3906, 1953 and 976. Now suppose that version 7 compiles version 976 successfully. So the failure with version 7 is between 976 and 1953. But since version 976 is stronger, you can start working forward with version 976. So it's like a binary search that's restarted whenever you get a "greater-than". Even if for some reason this were a manual process, each time you get a working version you at least halve the remaining space. Finally, as you said above, someone could make a batch file / shell script that literally goes through every commit in the version control system (not skipping any) and always use the previously working version on the next working version. A script doing so may well run in matter of days, though, depending on how long it takes to compile a the compiler compiler. Ordinarily there are a lot of commits! The binary search above cuts this down significantly. (However the binary search isn't theoretically guaranteed to be faster; after all theoretically we can imagine that version 7 compiles version 8 but fails on version 9; version 8 compiles version 9 but fails on version 10; etc. So theoretically every single commit could be breaking. (Theoretically.) But that's extremely unlikely to be the case. I don't imagine you'd have to do more than a few hundred compilations with the above binary-search methodology before you got one that started with version 7 but stepping through the commits in the way specified, produced a binary that compiles the latest version. The process may have to be partly manual due to breaking changes in semantics of invoking the compiler or its dependencies, but that should be rare. This process would also in the end allow you to do a bit-for-bit comparison of the output of the current version of the compiler when compiled using the above trusteable version, versus compiled from source code with the "trusting-trust" backdoor (where every version is backdoored and inserts a backdoor when compiling itself, without this backdoor being in the source code anywhere. so the above process would let you tell whether there's a trusting-trust backdoor, as long as there is a single early version that for sure didn't have it yet, and you have the commit history (from which the trusting-trust has been edited out). as I said above, if you don't have a single known-good version without the trusting-trust backdoor, then you'll have to write something that can compile version 2 or 3 (or 7) yourself, in another language.

rusbus 10y ago

Randomizing memory layouts and modifying the stack will have no impact since this attack isn't exploiting anything in the language, you've created a compiler that intentionally miscompiles source code. And not only does it miscompile source code, it miscompiles itself so that it preserves the exploit. One potential way to try to remove attacks like this is to run the source code of the compiler through something that randomizes the structure and text without changing how it actually functions. That way, you may be able to defeat the code that is trying to match on code that looks like the part of the compiler it's trying to hijack.

logicallee 10y ago

you use an old compiler binary that didn't have the attack yet to compile the latest source code that it is able to compile, then use that compile the latest it can compile, and so forth. what I mean is that I wouldn't expect a the 2012 rust prerelease to be able to compile the 2016 rust source code, but it can probably do 2013, use that to compile 2014, use that to compile 2015 use that to compile 2016. As long as you have a single binary from any point before the attack was introduced it shouldn't be an issue. The whole point is that at no point does the source code contain the trust backdoor, so you can just work forward from any binary that doesn't have it yet. if the very first version of rust binary already had it as an issue, as well as was written in rust, you could conceivably have a problem though. then you would need an alternative compiler, however sub-optimal it might be... or you could simply patch and remove the backdoor from the binary and then have it compile itself without inserting the backdoor.

Manishearth 10y ago
> but it can probably do 2013, use that to compile 2014, use that to compile 2015 use that to compile 2016. Clearly you aren't aware of Rust's history :) proto-Rust has been under so many rapid changes that each compiler usually only compiles with a specific hash. Now stuff works with a numbered Rust release, but that's a relatively new phenomenon. This process will likely need to go through hundreds of compilation steps. Doable, but not as simple as a year-by-year process.
- vog 10y ago
  I believe the year numbers were used by logicallee only as an example. Of course, if somebody is trying this, they need to figure out a different (smaller) time scale that actually works. In the worst case, you have to follow each commit in the version control system of the compiler, but I'm pretty sure you don't need to do it that fine grained.
  - logicallee 10y ago
    yes. I'm pretty shocked Manishearth didn't get that I was just giving examples of the process with placeholder dates, since I started my comment explicitly stating (I add emphasis here): >you use an old compiler binary that didn't have the attack yet to compile the latest source code that it is able to compile, then use that to compile the latest it can compile, and so forth. in trying to find the "latest source code that it is able to compile" you can do a binary search backward from the current version of the source code. it doesn't take long to find the latest version for each one (i.e. the latest each one compiles without error, into a working binary that passes some test suite). And anyway whenever you're binary-searching forward (i.e. after any point where the binary search yields ""greater-than" because the one you just tried compiled) then you can just use the version you just successfully compiled. Let me illustrate what i mean with this binary search: so if we're at version 1 million today, which the version 7 doesn't compile, then you try version 7 on version 500,000 (it'll fail), then on version 250,000 (it'll fail), version 125,000 (it'll fail), version 125,000 (it'll fail), version 62,500 (it'll fail), version 31,250 (it'll fail), version 62500 (fail), version 31250 (fail), versions, 15625, 7812, 3906, 1953 and 976. Now suppose that version 7 compiles version 976 successfully. So the failure with version 7 is between 976 and 1953. But since version 976 is stronger, you can start working forward with version 976. So it's like a binary search that's restarted whenever you get a "greater-than". Even if for some reason this were a manual process, each time you get a working version you at least halve the remaining space. Finally, as you said above, someone could make a batch file / shell script that literally goes through every commit in the version control system (not skipping any) and always use the previously working version on the next working version. A script doing so may well run in matter of days, though, depending on how long it takes to compile a the compiler compiler. Ordinarily there are a lot of commits! The binary search above cuts this down significantly. (However the binary search isn't theoretically guaranteed to be faster; after all theoretically we can imagine that version 7 compiles version 8 but fails on version 9; version 8 compiles version 9 but fails on version 10; etc. So theoretically every single commit could be breaking. (Theoretically.) But that's extremely unlikely to be the case. I don't imagine you'd have to do more than a few hundred compilations with the above binary-search methodology before you got one that started with version 7 but stepping through the commits in the way specified, produced a binary that compiles the latest version. The process may have to be partly manual due to breaking changes in semantics of invoking the compiler or its dependencies, but that should be rare. This process would also in the end allow you to do a bit-for-bit comparison of the output of the current version of the compiler when compiled using the above trusteable version, versus compiled from source code with the "trusting-trust" backdoor (where every version is backdoored and inserts a backdoor when compiling itself, without this backdoor being in the source code anywhere. so the above process would let you tell whether there's a trusting-trust backdoor, as long as there is a single early version that for sure didn't have it yet, and you have the commit history (from which the trusting-trust has been edited out). as I said above, if you don't have a single known-good version without the trusting-trust backdoor, then you'll have to write something that can compile version 2 or 3 (or 7) yourself, in another language.