4 ms·

I am not sure to understand how the program can make a distinction between 33 C0 (because it is written as 33 C0) and 33 C0 (because it was written as 31 C0 and

by jaclaz 6y ago

I am not sure to understand how the program can make a distinction between 33 C0 (because it is written as 33 C0) and 33 C0 (because it was written as 31 C0 and was later changed by steg86 to 33 C0)? Or, seen the other way, maybe steg86 can "extract" (from already existing untouched binaries) secret messages that were never intentionally written?

woodruffw 6y ago
This is a really good question! steg86 currently embeds a 32-bit header for itself. You can see the relevant constants here[1]. If the header doesn't validate during extraction, steg86 fails instead of extracting potential garbage. [1]: https://github.com/woodruffw/steg86/blob/master/src/steg86/binary.rs#L12-L24 https://github.com/woodruffw/steg86/blob/master/src/steg86/b...
- jaclaz 6y ago
  OK, but how is the 32-bit header itself embedded? The header is a good thing for preventing accidental extraction from binaries not treated with steg86, but still you need to modify 4 bytes (or 4 instructions) to embed this header, so - at least theorically - the possibility of a "collision" or of a false positive seems relatively high to me.
  - woodruffw 6y ago
    > OK, but how is the 32-bit header itself embedded? The header is embedded according to the same rules as the rest of the message: it's treated as a bitstring, and flippable instructions are flipped appropriately to encode it. > the possibility of a "collision" or of a false positive seems relatively high to me. As others have pointed out, compilers (and assemblers) tend to stick to a single selection choice for register-to-register ops. Even in the case where a compiler writer flips between them randomly, their 32 random choices would have to align precisely with the expected header. It's certainly not impossible, but pretty unlikely. It's also completely remediable with a CRC32 or similar field tacked onto the header; I just didn't think the likelihood warranted that for the initial design.
  - paraboul 6y ago
    4 bytes of the encoded header isn't 4 instructions, it's 32 consecutive instructions that each translate to a bit depending on their semantic form. So there is virtually no chance for a compiler to generate a valid sequence randomly.
    - jaclaz 6y ago
      I see, each changed instruction gives a single bit (not byte) of information, my bad.
- Legogris 6y ago
  But that's not a fundamental issue of the idea and rather a quirk in the steg86 implementation, right?
  - woodruffw 6y ago
    Which part? The header is specific to steg86, and some of its constraints (like the maximum message size) are a product of that. Otherwise, there aren't any quirks in the implementation that I'm currently aware of.
- Legogris 6y ago
  Are there other semantic duals in the instruction sets? If so, when combined with cryptography, it would offer some additional level of plausible deniability over which of the possible messages (due to parameter selection) is the cryptotext.
  - jlokier 6y ago
    The two most obvious are: - Register allocation choices - Instruction ordering choices
    - schoen 6y ago
      Also conditional branches because you can conceivably do the comparison, branch, and fall-through in several different ways. Consider the initial case cmp ax,bx jge foo bar: ; code that gets run if ax < bx foo: ; code that gets run if ax >= bx You could change this to cmp bx,ax and then change the jge to jl, or you could change either one alone and reverse the order of the bar and foo code blocks, or you could change both and not reverse the order of the bar and foo code blocks. (You have fewer choices if you are doing the comparison as the exit condition for a loop, except sometimes compilers will put the loop continue condition as an unconditional jump after bar or foo, in which case you have even more choices, like whether to do that or not!)
shawnz 6y ago
The same problem is faced when you present basically any kind of encryption scheme with random data. It would be easy to fix that kind of problem by adding a checksum to the secret message. Besides, in what scenario would you be decrypting arbitrary binaries with this, such that it would be a problem for you to have false positives? Just make sure to use it only on files which you know contain secret messages.
- jaclaz 6y ago
  >Besides, in what scenario would you be decrypting arbitrary binaries with this, such that it would be a problem for you to have false positives? Just make sure to use it only on files which you know contain secret messages. Well, more or less cryptography/steganography can be used to either store "secrets" or to communicate them. If I used something like this to communicate, I would probably tell the other part to download (say) a .iso full of binaries, as opposed to a single binary.

by jaclaz 6y ago

woodruffw 6y ago

This is a really good question! steg86 currently embeds a 32-bit header for itself. You can see the relevant constants here[1]. If the header doesn't validate during extraction, steg86 fails instead of extracting potential garbage. [1]: https://github.com/woodruffw/steg86/blob/master/src/steg86/binary.rs#L12-L24 https://github.com/woodruffw/steg86/blob/master/src/steg86/b...

jaclaz 6y ago
OK, but how is the 32-bit header itself embedded? The header is a good thing for preventing accidental extraction from binaries not treated with steg86, but still you need to modify 4 bytes (or 4 instructions) to embed this header, so - at least theorically - the possibility of a "collision" or of a false positive seems relatively high to me.
- woodruffw 6y ago
  > OK, but how is the 32-bit header itself embedded? The header is embedded according to the same rules as the rest of the message: it's treated as a bitstring, and flippable instructions are flipped appropriately to encode it. > the possibility of a "collision" or of a false positive seems relatively high to me. As others have pointed out, compilers (and assemblers) tend to stick to a single selection choice for register-to-register ops. Even in the case where a compiler writer flips between them randomly, their 32 random choices would have to align precisely with the expected header. It's certainly not impossible, but pretty unlikely. It's also completely remediable with a CRC32 or similar field tacked onto the header; I just didn't think the likelihood warranted that for the initial design.
- paraboul 6y ago
  4 bytes of the encoded header isn't 4 instructions, it's 32 consecutive instructions that each translate to a bit depending on their semantic form. So there is virtually no chance for a compiler to generate a valid sequence randomly.
  - jaclaz 6y ago
    I see, each changed instruction gives a single bit (not byte) of information, my bad.
Legogris 6y ago
But that's not a fundamental issue of the idea and rather a quirk in the steg86 implementation, right?
- woodruffw 6y ago
  Which part? The header is specific to steg86, and some of its constraints (like the maximum message size) are a product of that. Otherwise, there aren't any quirks in the implementation that I'm currently aware of.
Legogris 6y ago
Are there other semantic duals in the instruction sets? If so, when combined with cryptography, it would offer some additional level of plausible deniability over which of the possible messages (due to parameter selection) is the cryptotext.
- jlokier 6y ago
  The two most obvious are: - Register allocation choices - Instruction ordering choices
  - schoen 6y ago
    Also conditional branches because you can conceivably do the comparison, branch, and fall-through in several different ways. Consider the initial case cmp ax,bx jge foo bar: ; code that gets run if ax < bx foo: ; code that gets run if ax >= bx You could change this to cmp bx,ax and then change the jge to jl, or you could change either one alone and reverse the order of the bar and foo code blocks, or you could change both and not reverse the order of the bar and foo code blocks. (You have fewer choices if you are doing the comparison as the exit condition for a loop, except sometimes compilers will put the loop continue condition as an unconditional jump after bar or foo, in which case you have even more choices, like whether to do that or not!)

shawnz 6y ago

The same problem is faced when you present basically any kind of encryption scheme with random data. It would be easy to fix that kind of problem by adding a checksum to the secret message. Besides, in what scenario would you be decrypting arbitrary binaries with this, such that it would be a problem for you to have false positives? Just make sure to use it only on files which you know contain secret messages.

jaclaz 6y ago
>Besides, in what scenario would you be decrypting arbitrary binaries with this, such that it would be a problem for you to have false positives? Just make sure to use it only on files which you know contain secret messages. Well, more or less cryptography/steganography can be used to either store "secrets" or to communicate them. If I used something like this to communicate, I would probably tell the other part to download (say) a .iso full of binaries, as opposed to a single binary.