Based on ideas from https://stackoverflow.com/questions/7743534/filter-search-and-replace-array-of-bytes-in-an-inputstream, but a bit more efficient by avoiding a lot of allocation for each processed byte. Still not great, but good enough for my usecase.

ByteReplacingInputStream.java

import java.io.FilterInputStream;
import java.io.IOException;
import java.io.InputStream;

/** A bit more efficient byte replacing filter stream */
public class ByteReplacingInputStream extends FilterInputStream {

    private final byte[] search, replacement;
    private byte[] buffer;
    private int bufferOffset, bufferEOL, replacementOffset;

    public ByteReplacingInputStream(InputStream in, byte[] search, byte[] replacement) {
        super(in);
        this.search = search;
        this.replacement = replacement;

        // Buffer fits the search string a single time
        buffer = new byte[this.search.length];

        // Init rest of state
        bufferOffset = 0;
        bufferEOL = -1;

        // Setting replacementOffset to trigger a fillBuffer at first read
        replacementOffset = this.replacement.length;
    }

    @Override
    public int read() throws IOException {
        // If we just finished a replacement output run, refill the buffer
        if(replacementOffset >= replacement.length) {
            bufferOffset = 0;
            bufferEOL = -1;
            replacementOffset = -1;
            for (byte i = 0; i < buffer.length; i++) {
                int b = super.read();
                if (b == -1) {
                    bufferEOL = i;
                    break;
                } else {
                    buffer[i] = (byte) b;
                }
            }
        }

        // Once we reach the EOL, there is nothing left to be done
        if(bufferOffset == bufferEOL) {
            return -1;
        }

        // If we're not inside a replacement, should we start one right now?
        if(replacementOffset < 0) {
            boolean match = true;
            for (byte i = 0; i < search.length; i++) {
                if (buffer[(bufferOffset + i) % buffer.length] != search[i]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                replacementOffset = 0;
            }
        }

        // Output a replacement byte
        if(replacementOffset >= 0) {
            if(replacementOffset < replacement.length) {
                return replacement[replacementOffset++];
            } else {
                // The replacement appears to be zero.
                // We're normally jump to the top, but since we don't have goto's in Java, we instead just recurse
                return read();
            }
        }

        // We will now read a byte from the normal buffer
        int result = buffer[bufferOffset];

        // If we haven't found the EOL yet, this is the time to read a new byte
        if(bufferEOL < 0) {
            int b = super.read();
            if (b == -1) {
                bufferEOL = bufferOffset;
            } else {
                buffer[bufferOffset] = (byte) b;
            }
        }

        // We increase the offset
        bufferOffset = (bufferOffset + 1) % buffer.length;

        // Return the normal byte
        return result;
    }

    @Override
    public int read(byte b[]) throws IOException {
        return read(b, 0, b.length);
    }

    @Override
    public int read(byte b[], int offset, int length) throws IOException {
        // Standard implementation from Java
        if (b == null) {
            throw new NullPointerException();
        } else if (offset < 0 || length < 0 || length > b.length - offset) {
            throw new IndexOutOfBoundsException();
        } else if (length == 0) {
            return 0;
        }

        int c = read();
        if (c == -1) {
            return -1;
        }
        b[offset] = (byte) c;

        int i = 1;
        try {
            for (; i < length ; i++) {
                c = read();
                if (c == -1) {
                    break;
                }
                b[offset + i] = (byte) c;
            }
        } catch (IOException e) {}

        return i;
    }
}