Watermarking: Difference between revisions

From NESdev Wiki
Jump to navigationJump to search
(→‎Shuffling: EPIC win)
m (→‎See also: Concentration Room moved to userspace)
 
(19 intermediate revisions by 5 users not shown)
Line 1: Line 1:
'''Watermarking''' is [[wikipedia:Digital watermarking|defined by Wikipedia]] as "the process of embedding information into a digital signal in a way that is difficult to remove."
'''Watermarking''' is [[wikipedia:Digital watermarking|defined by Wikipedia]] as "the process of embedding information into a digital signal in a way that is difficult to remove."
In some cases, the developer of an unreleased NES program wants to distribute to beta testers but still trace any [[wikipedia:Internet leak|leaked]] copies of the program to the tester who broke the non-disclosure agreement.
In some cases, the developer of an unreleased NES program wants to distribute copies to beta testers but still [[wikipedia:Traitor tracing|trace]] any [[wikipedia:Internet leak|leaked]] copies of the program to the tester who broke the non-disclosure agreement.
There are several ways to produce binaries that can be traced back to a particular recipient.
There are several ways to produce binaries that can be traced back to a particular recipient.


Line 8: Line 8:
A code preprocessor can randomize the order of statically allocated variables in a program.
A code preprocessor can randomize the order of statically allocated variables in a program.
This causes the addresses embedded in the code to change every time the program is compiled.
This causes the addresses embedded in the code to change every time the program is compiled.
It has benefits beyond watermarking: as the program is shuffled, the effects of a [[wikipedia:buffer overflow|buffer overflow]] may become more apparent.
It has benefits beyond watermarking: as the program is shuffled, a randomly chosen variable acts as a [[wikipedia:Buffer overflow protection|canary]] for the variable before it, and the effects of a [[wikipedia:buffer overflow|buffer overflow]] may become more apparent.


A code preprocessor can shuffle the order of subroutines in a program.
A code preprocessor can shuffle the order of subroutines or lookup tables in a program.
Watch out: A common technique on the NES is the "[[wikipedia:Inline expansion|inline]] [[wikipedia:tail call|tail call]]", in which a subroutine doesn't return but instead falls off the end into the following subroutine.
Watch out: A common technique on the NES is the "[[wikipedia:Inline expansion|inline]] [[wikipedia:tail call|tail call]]", in which a subroutine doesn't return but instead falls off the end into the following subroutine.
You'll need to take this into account when adding markup to control the preprocessor.
You'll need to take this into account when adding markup to control the preprocessor.
Line 16: Line 16:
A code preprocessor can shuffle the order of instructions in a subroutine.
A code preprocessor can shuffle the order of instructions in a subroutine.
In a lot of cases, the order of instructions doesn't matter, such as <code>LDA</code> vs. <code>CLC</code>, or <code>LDX</code> vs. <code>LDY</code> where neither is indexed, or <code>STA (d),Y</code> vs. <code>DEX</code>, or STA of the same value to several different variables.
In a lot of cases, the order of instructions doesn't matter, such as <code>LDA</code> vs. <code>CLC</code>, or <code>LDX</code> vs. <code>LDY</code> where neither is indexed, or <code>STA (d),Y</code> vs. <code>DEX</code>, or STA of the same value to several different variables.
Writes to some [[PPU registers]] act similarly: when setting up $2000 and $2001 at the end of vertical blanking, it doesn't matter which is written first.
Writes to some [[PPU registers]] act similarly: when setting up [[PPUCTRL]] ($2000) and [[PPUMASK]] ($2001) at the end of vertical blanking, it doesn't matter which is written first.
The markup for such "bundles of instructions" resembles the markup for [[wikipedia:explicitly parallel instruction computing|explicitly parallel instruction computing]].
The markup for such "bundles of instructions" resembles the markup for stop bits in [[wikipedia:explicitly parallel instruction computing|explicitly parallel instruction computing]].
Adding the required markup also has a benefit beyond watermarking: it forces a code review, which allows a programmer to refamiliarize himself with a code base and possibly discover defects.
Adding the required markup also has a benefit beyond watermarking: thinking about what instructions affect others forces a code review, which allows a programmer to refamiliarize himself with a code base and possibly discover defects.


A common method to cope with bus conflicts on discrete [[mapper]]s brings in another trick.
A common method to cope with bus conflicts on discrete [[mapper]]s brings in another trick.
Line 30: Line 30:


== Instruction encoding ==
== Instruction encoding ==
A few instructions have [[Programming_with_unofficial_opcodes#Watermarking_instructions|multiple encodings]].
A few instructions have [[Programming_with_unofficial_opcodes#Duplicated_instructions|multiple encodings]].
A code preprocessor can introduce any of several NOP instructions at random points in a non-time-critical subroutine.
A code preprocessor can introduce any of several [[Programming_with_unofficial_opcodes#NOPs|NOP instructions]] at random points in a non-time-critical subroutine.
 
One may also add official do-(near)-nothing instructions such as EOR #0, ORA #0, AND #$FF, an INX/DEX pair, etc. Another watermarking padding stratagem would be, before a load instruction for a register (LDA, LDX, LDY, PLA, TAX, TAY, TSX, TXA, or TYA), to introduce instructions affecting that register; the load makes irrelevant all changes to the register's contents. One should, of course, take care to ensure that such new instructions do not have undesired flag changes altering execution flow.
 
The addresses of the PPU's ports, almost every mapper without [[bus conflict]]s, and the internal WRAM are all [[mirroring|incompletely decoded]].
Because the NES PPU is configured to ignore A12 through A3, each PPU port appears 1024 times in the range $2000-$3FFF.
Likewise, the [[MMC3]] ignores A12 through A1, and each port appears 4096 times.
The [[MMC1]] ignores A14 through A0 for the first four writes and A12 through A0 for the last, or 73 bits in all, but many games use only one subroutine to handle all writes to each of its four ports.
The internal RAM appears only 4 times in $0000-$1FFF, but any non-zero-page instruction could be changed to use one of the mirrors.
A code preprocessor could randomize these address bits in any instruction that reads or writes these ports.
This would also serve to hinder a cracker's use of an in-emulator debugger that doesn't take mirroring into account.
 
Use of multiple instruction encoding and multiple address decoding might also be used if you want to store the program and data in the same place (although this is difficult), or to use the mirrored registers for some purpose in a mapper that you might make up or in a debugger.


== Graphics changes ==
== Graphics changes ==
Graphics can depend on the build:
Graphics can depend on the build:
*Choose one of several alternatives for [http://www.petesqbsite.com/sections/tutorials/tuts/tsugumo/chapter1.htm grass] and other [http://www.petesqbsite.com/sections/tutorials/tuts/tsugumo/chapter3.htm noisy tiles]
*Choose one of several alternatives for [http://www.petesqbsite.com/sections/tutorials/tuts/tsugumo/chapter1.htm grass] and other [http://www.petesqbsite.com/sections/tutorials/tuts/tsugumo/chapter3.htm noisy tiles]
*Rearrange the order in which sets of tiles appear in the CHR ROM
*Tester's name or something derived from tester's name on the title screen. This is easy to remove, but it acts as a deterrent.
*Tester's name or something derived from tester's name on the title screen. This is easy to remove, but it acts as a deterrent.
*Tester's name or something derived from tester's name on a sign in a building in the game
*Tester's name or something derived from tester's name on a sign in a building in the game
Line 41: Line 54:
== Compression ==
== Compression ==
If your program includes compressed data, you can change the interpretation of bits in the data format.
If your program includes compressed data, you can change the interpretation of bits in the data format.
For example, in RLE compression of graphics, the sense of bits denoting a run of repeated pixels vs. bits denoting a run of several literal pixels can be inverted.
For example, in RLE [[tile compression]], the sense of bits denoting a run of repeated pixels vs. bits denoting a run of several literal pixels can be inverted.
 
== See also ==
*[[User:Tepples/Concentration Room|Concentration Room]]: Version 0.02 includes a Python program to shuffle source code, and an example of how to work it into a makefile.
 
== External links ==
*Based on BBS topics [http://forums.nesdev.org/viewtopic.php?t=6046 6046] and [http://forums.nesdev.org/viewtopic.php?t=6197 6197]

Latest revision as of 00:25, 18 March 2023

Watermarking is defined by Wikipedia as "the process of embedding information into a digital signal in a way that is difficult to remove." In some cases, the developer of an unreleased NES program wants to distribute copies to beta testers but still trace any leaked copies of the program to the tester who broke the non-disclosure agreement. There are several ways to produce binaries that can be traced back to a particular recipient.

Shuffling

One way to make each copy unique is to shuffle, or randomly rearrange, pieces of a program at compile time.

A code preprocessor can randomize the order of statically allocated variables in a program. This causes the addresses embedded in the code to change every time the program is compiled. It has benefits beyond watermarking: as the program is shuffled, a randomly chosen variable acts as a canary for the variable before it, and the effects of a buffer overflow may become more apparent.

A code preprocessor can shuffle the order of subroutines or lookup tables in a program. Watch out: A common technique on the NES is the "inline tail call", in which a subroutine doesn't return but instead falls off the end into the following subroutine. You'll need to take this into account when adding markup to control the preprocessor.

A code preprocessor can shuffle the order of instructions in a subroutine. In a lot of cases, the order of instructions doesn't matter, such as LDA vs. CLC, or LDX vs. LDY where neither is indexed, or STA (d),Y vs. DEX, or STA of the same value to several different variables. Writes to some PPU registers act similarly: when setting up PPUCTRL ($2000) and PPUMASK ($2001) at the end of vertical blanking, it doesn't matter which is written first. The markup for such "bundles of instructions" resembles the markup for stop bits in explicitly parallel instruction computing. Adding the required markup also has a benefit beyond watermarking: thinking about what instructions affect others forces a code review, which allows a programmer to refamiliarize himself with a code base and possibly discover defects.

A common method to cope with bus conflicts on discrete mappers brings in another trick. For example, a game using UNROM might load from a table and write back to that table to make sure that the written bits match the bits in ROM. (See the banktable example at Programming UNROM.) But if you shuffle the data in banks 0 through 6 and shuffle the bank numbers in the table, you can make 7! = 5040 different binaries from this alone.

Even in a game no bigger than NROM-128, shuffling alone allows for more distinct binaries than the number of atoms in the known universe squared. With the size of NES games and with modern solid archiving tools such as 7-Zip, you can save each binary that you send out to each tester and still not fill a 4 GB USB flash drive. As long as the binary doesn't get leaked to someone with the knowledge to disassemble and reassemble a binary (as in SMBDis), computing the Hamming distance between the leaked copy and your saved copies is likely to result in a high-confidence match to the leaker.

Instruction encoding

A few instructions have multiple encodings. A code preprocessor can introduce any of several NOP instructions at random points in a non-time-critical subroutine.

One may also add official do-(near)-nothing instructions such as EOR #0, ORA #0, AND #$FF, an INX/DEX pair, etc. Another watermarking padding stratagem would be, before a load instruction for a register (LDA, LDX, LDY, PLA, TAX, TAY, TSX, TXA, or TYA), to introduce instructions affecting that register; the load makes irrelevant all changes to the register's contents. One should, of course, take care to ensure that such new instructions do not have undesired flag changes altering execution flow.

The addresses of the PPU's ports, almost every mapper without bus conflicts, and the internal WRAM are all incompletely decoded. Because the NES PPU is configured to ignore A12 through A3, each PPU port appears 1024 times in the range $2000-$3FFF. Likewise, the MMC3 ignores A12 through A1, and each port appears 4096 times. The MMC1 ignores A14 through A0 for the first four writes and A12 through A0 for the last, or 73 bits in all, but many games use only one subroutine to handle all writes to each of its four ports. The internal RAM appears only 4 times in $0000-$1FFF, but any non-zero-page instruction could be changed to use one of the mirrors. A code preprocessor could randomize these address bits in any instruction that reads or writes these ports. This would also serve to hinder a cracker's use of an in-emulator debugger that doesn't take mirroring into account.

Use of multiple instruction encoding and multiple address decoding might also be used if you want to store the program and data in the same place (although this is difficult), or to use the mirrored registers for some purpose in a mapper that you might make up or in a debugger.

Graphics changes

Graphics can depend on the build:

  • Choose one of several alternatives for grass and other noisy tiles
  • Rearrange the order in which sets of tiles appear in the CHR ROM
  • Tester's name or something derived from tester's name on the title screen. This is easy to remove, but it acts as a deterrent.
  • Tester's name or something derived from tester's name on a sign in a building in the game

Compression

If your program includes compressed data, you can change the interpretation of bits in the data format. For example, in RLE tile compression, the sense of bits denoting a run of repeated pixels vs. bits denoting a run of several literal pixels can be inverted.

See also

  • Concentration Room: Version 0.02 includes a Python program to shuffle source code, and an example of how to work it into a makefile.

External links