1

I want to obfuscate a string using Linear Feedback Shift Register, so I am trying to understand the below code of wiki In the below wiki example of Linear Feedback Shift Register ,'0xACE1u' is the hex value used as start state, But I didnt understand what is this 0xB400u ?

Could somebody plesae explain what is that? and any link which explains how to use LFSR to obfuscate strings would be appreciated

int main(void)
{
    uint16_t start_state = 0xACE1u;  /* Any nonzero start state will work. */
    uint16_t lfsr = start_state;
    unsigned period = 0;

    do
    {
        unsigned lsb = lfsr & 1;   /* Get LSB (i.e., the output bit). */
        lfsr >>= 1;                /* Shift register */
        if (lsb) {                 /* If the output bit is 1, apply toggle mask. */
            lfsr ^= 0xB400u;
        }
        ++period;
    } while (lfsr != start_state);

    return 0;
}
Ravi Kiran
  • 219
  • 3
  • 14

1 Answers1

5

The Wikipedia article you got this from has an illustration that explains what the code is doing:

16-bit LFSR

The least significant bit extracted from the end of the shift register is fed back by XOR-ing it with bits 16, 14, 13 and 11. When this bit is zero, this has no effect, but when it is 1, all these bits are flipped. The quickest way of doing this is by calculating the XOR product of the 16-bit shift register with 0xB400, which has all of these bits set (1011010000000000 in binary).

(Note: There is no XOR gate feeding into bit 16 because there is no input from bit 17.)

Other LFSRs:

This page contains lists of feedback constants that work with LFSRs of different lengths. The list of 16-bit LFSRs has 2048 entries.

Obfuscating data with an LFSR:

As long as your LSFR initially contains a non-zero value, it will step through a sequence of 65535 (216–1) pseudorandom values at every iteration. Just XOR these values with your data to obfuscate it, and repeat the process using the same sequence of numbers to retrieve the original data. To obfuscate a series of byte values, you might find it easier to extract just 8 bits at each iteration.

Here's some example code that will do the job. If you are obfuscating a text string, you will need to keep track of its length because it is quite likely that the obfuscated string will contain null bytes:

#include <stdio.h>
#include <string.h>

/* In-place string obfuscation */
void lfsr16_obfuscate(char *s, int length, unsigned short seed) {
    int i, lsb;

    for (i=0; i<length; i++) {
        s[i] ^= seed & 0x00ff;
        lsb = seed & 1;
        seed >>= 1;
        if (lsb) seed ^= 0xB400u;
    }
}


int main(void) {
    int i, n;
    char message[] = "Hello world";

    printf("Original message: %s\n", message);
    n = strlen(message);

    /* Obfuscate the message */
    lfsr16_obfuscate(message, strlen(message), 0xACE1u);
    printf("Obfuscated results (in hex):");
    for (i=0; i<n; i++) printf(" %02hhx", message[i]);
    putchar('\n');

    /* Repeat the obfuscation process to retrieve original message */
    lfsr16_obfuscate(message, strlen(message), 0xACE1u);
    printf("Recovered message: %s\n", message);

    return 0;
}
r3mainer
  • 23,981
  • 3
  • 51
  • 88
  • Thx for your reply, So I can use the same '0xB400' to xor with , even in my code? or 0xB400 this varies based on the input ? – Ravi Kiran Jun 16 '17 at 08:31
  • 0xb400 is a value that gives you a maximal length sequence with a 16-bit shift register. For a LFSR with a different number of bits, you will need to use a different constant. – r3mainer Jun 16 '17 at 08:33
  • Got it, thank u, Now I need to obfuscate a string using 16 bit LFSR, but I dont see any input variable in the above wiki example I posted, could you please tell me how could I pass my input string (or hex value of my input string) ? – Ravi Kiran Jun 16 '17 at 08:53
  • one more clarification please, why are we doing seed & 0x00ff; – Ravi Kiran Jun 16 '17 at 09:45
  • To extract the lower 8 bits of the seed value – r3mainer Jun 16 '17 at 09:48