A "proper" search while still retaining sufficiently-looking randomness might be achievable via an SMT solver, by asking it to find an index above the current position, below a binary-searched top boundary, that contains the search term. I think SMT solvers should be clever enough to be able to work the search around some ciphers.
Maybe an SMT solver is a rather heavy-weight approach, but I think it fits the task of searching through 2^122 values :)
Edit: even with no cipher, it takes said approach ~1.6s to find that after 0x1067D3DC2F4951AEA8DB8D0108D7D65 the first occurrence of 0xABCD is at 0x1067D3DC2F4951AEA8DB8D0108DABCD with Z3 (cvc5 and Bitwuzla are slightly slower), which is perhaps a bit too slow.. perhaps it could be improved to something more reasonable by restricting the search to near the end until that fails, and reducing the matchable positions based on the dashes, but that's back to effort.
Edit 2: slightly more effort later:
cipher: 0x15FD586DF0CE258730098B94325ACE7 * (val ^ 0x93C324915DB2B3C4D4CD8135C0DDF1)
inverse: (0x1D52334877384DE3A6DAA4A3312A6D7 * val) ^ 0x93C324915DB2B3C4D4CD8135C0DDF1
example first 10 entries:
0: 2839676B79617D5B9FDF9D43CFB3077
1: 123C0EFD889357D46FD611AF9D58390
2: 143418475AFDC869FFF2B46C3468A45
3: 3E36BFD96A2FA2E2CFE928D8020DD5E
4: 002EC9233C9A13786005CB94991E413
5: 2A3170B54BCBEDF12FFC400066C372C
6: 2C2979FF1E365E86C018E2BCFDD3DE1
7: 162C21912D6838FF900F5728CB790FA
8: 18242ADAFFD2A995202BF9E562897AF
9: 0226D26D0F04840DF0226E51302EAC8
binary search max set to `10 * 2**search_bit_width` after after the chosen start
trying to find a match only in the last 3 possible places (i.e. searching WXYZ only matches *****WXYZ, ****WXYZ*, ***WXYZ**)
searching for 0xFF00FFCC after index 0xAAAAAAAAAAAAAA:
nearest match found at: 0xAAAAAAAD04E3DA
ciphered: 0x0E9399CC39B716BC96348AFF00FFCCD
time taken: 0.7s (bitwuzla or cvc5), or 1s (z3)
But alas I'm stupid, and searching doesn't care about lexicographic ordering, and you necessarily have to search all possible places, not just the end, and that's a ton slower. Perhaps dash placement could reduce them enough, but that's even more effort.
Maybe an SMT solver is a rather heavy-weight approach, but I think it fits the task of searching through 2^122 values :)
Edit: even with no cipher, it takes said approach ~1.6s to find that after 0x1067D3DC2F4951AEA8DB8D0108D7D65 the first occurrence of 0xABCD is at 0x1067D3DC2F4951AEA8DB8D0108DABCD with Z3 (cvc5 and Bitwuzla are slightly slower), which is perhaps a bit too slow.. perhaps it could be improved to something more reasonable by restricting the search to near the end until that fails, and reducing the matchable positions based on the dashes, but that's back to effort.
Edit 2: slightly more effort later:
But alas I'm stupid, and searching doesn't care about lexicographic ordering, and you necessarily have to search all possible places, not just the end, and that's a ton slower. Perhaps dash placement could reduce them enough, but that's even more effort.