LSB linear

The baseline steganography scheme. Walk the cover's sample bytes in storage order, overwrite the density least-significant bits of each byte with the next bits of the payload. The cover's top bits — which carry almost all the visual / audible signal — are untouched.

What "LSB" means

A byte has eight bits: b7 b6 b5 b4 b3 b2 b1 b0. b7 is the most-significant bit (worth 128), b0 is the least-significant (worth 1). For an 8-bit sample — one channel of an RGB pixel, one mono audio sample, an index into a palette — flipping b0 changes the sample by ±1. That's a 1/256 change on any given byte.

The human visual system can't tell #A3A3A3 from #A2A3A3 at a normal viewing distance. The ear can't tell a 16-bit PCM sample with value 23414 from 23415. Density ≥ 2 widens the budget — four times the capacity at density 4 — but also widens the worst-case perceptual delta to ±7 for an 8-bit sample, which starts to show as banding on smooth gradients.

What "linear" means

We visit carrier bytes in the exact order they appear in the file. For rsteg-bmp that's "skip the 54-byte file header, then walk every byte of the pixel array left-to-right, top-to-bottom" — see crates/rsteg-bmp/src/lib.rs. We don't skip padding bytes inside a row, because 24-bit BMP rows are 4-byte-aligned and the BMP header's biSizeImage field tells the extractor exactly how many pixel bytes there are.

The n-th payload bit lands in the density low bits of sample byte ⌊n / density⌋. Extract does the reverse: read the LSBs from samples 0..ceil(framed_bits / density) back into a bitstream, parse the 32-byte PayloadHeader, keep reading body_len more bytes.

Visualization 1 — payload bits land in sample LSBs

Sixteen cover bytes, each shown as eight bits. The LSB column is highlighted. Below, a two-byte payload 0x48 0x69 (= "Hi") as a 16-bit stream. Arrows show which payload bit lands in which LSB. Green markers flag bytes whose LSB flipped; gray = unchanged (the cover's original LSB already matched the payload bit).

cover bytes (before embed) — 16 samples, binary MSB→LSB b0 1 0 1 0 0 0 1 1 flip→0 b1 0 1 1 1 0 1 0 1 keep b2 1 1 0 0 1 1 1 0 keep b3 0 0 0 1 1 0 1 1 flip→0 b4 1 0 0 0 1 0 0 0 flip→1 b5 0 1 0 0 0 0 1 0 keep b6 1 1 1 1 0 0 0 1 flip→0 b7 0 0 1 0 0 1 1 0 keep b8 1 0 1 0 1 0 1 1 flip→0 b9 1 1 0 1 0 0 1 0 flip→1 b10 0 0 1 1 0 1 1 0 flip→1 b11 0 1 1 1 0 1 0 1 flip→0 b12 1 0 0 1 0 1 1 1 keep b13 1 1 0 1 1 0 1 1 flip→0 b14 0 1 0 0 1 1 0 0 keep b15 1 0 1 1 0 1 0 0 flip→1 payload bits (MSB→LSB): 0x48 = 01001000, 0x69 = 01101001 → "Hi" 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 each cell → the LSB of one cover byte, in order →b0 →b1 →b2 →b3 →b4 →b5 →b6 →b7 →b8 →b9 →b10 →b11 →b12 →b13 →b14 →b15 11 of 16 bytes flipped — for a random cover, expected flips ≈ 8/16 (half the LSBs already happen to match). density = 1 here. At density 4 each payload byte fits into 2 cover bytes (8 bits / 4 bits-per-sample). cover bytes after embed carry a bitstream that decodes back to 0x48 0x69 = "Hi". Upper 7 bits unchanged.
LSB — writable channel payload bit flip — LSB changed keep — LSB already matched

Visualization 2 — capacity scales linearly with density

For N sample bytes and density D, the carrier holds floor(N·D / 8) payload bytes. On a 256×256 24-bit BMP that's N = 256·256·3 = 196 608 sample bytes. Subtract the 32-byte PayloadHeader and the maximum body is:

density body capacity (bytes) 1 24 544 body + 32 header = 24 576 2 49 120 body 3 73 696 body 4 98 272 body N = 196 608 sample bytes (256×256 RGB). capacity = floor(N·D / 8) − 32 bytes header. trade-off: density 4 is 4× capacity and ~4× the perceptual delta. density 1 is the recommended default.

The Rust that does this

The whole walk lives in rsteg-bmp/src/lib.rs. Simplified: 

// Embed: for each byte of `framed`, split into `density` bits, OR each bit into the
// LSBs of the next cover sample. Upper bits are preserved via a mask.
let mask: u8 = !((1 << density) - 1);   // density=1 → 0xFE, density=4 → 0xF0
for (sample, payload_bits) in cover_samples.iter_mut().zip(bit_reader) {
    *sample = (*sample & mask) | payload_bits;
}

// Extract: inverse. Read `density` low bits from each sample, append to a BitWriter.
for sample in stego_samples.iter().take(needed) {
    bw.write_bits(*sample & !mask, density);
}

bit_reader is rsteg-core::bits::BitReader, which unpacks a byte-stream into an iterator of D-bit chunks in MSB-first order. The framed bitstream is always header (32 B) || body. Extract reads 32·8/D samples, decodes the header, then reads body_len more bytes.

When this is and isn't a good idea

Linear LSB is the right default when there's no adversary: shipping configuration to yourself through an image that roundtrips a lossy pipeline, a demo that just needs to prove the mechanism works, a smoke test for the file-format adapter. It is not a good default when someone might run a steganalyser over your carrier.

The weakness isn't the bit-flipping — the LSB of a natural image is close to uniform noise so the flips are statistically invisible in aggregate. The weakness is that payload bits occupy a contiguous prefix of the carrier. Run chi-square on the first 1 000 samples vs. the last 1 000 and the prefix looks like forced uniformity while the suffix looks like natural image noise. Any undergraduate steganalysis tool flags this.

That's exactly why LSB permuted exists — same bit-flipping mechanic, passphrase-seeded walk order, so no contiguous block has a signal. That page has an interactive visualization of the walk.