Results 1 to 5 of 5

Thread: Berlekamp–Massey algorithm

  1. #1
    Senior Member

    Join Date
    Apr 2012
    Location
    14 Wombat Cres, Goanna Heights NSW
    Posts
    1,403
    Thanks
    728
    Thanked 1,150 Times in 576 Posts
    Rep Power
    602
    Reputation
    20563

    Default Berlekamp–Massey algorithm

    Anyone here familiar with the "Berlekamp–Massey algorithm"?

    I have the input/result of a 64-bit LFSR routine but I need to know the polynomial being used so I can code for it, I found this...



    ...which will apparently reverse-engineer a LFSR, but I just get lost in the algebra, so I really hope one of the brains trust here can help?

    I have two captured samples, #1:

    Code:
    hex input  = C3 80 9C 4B FA C0 85 EA
    hex output = 41 5D A3 43 A8 2F 07 49
    And sample #2:

    Code:
    hex input  = 50 15 F1 C1 AD 7F EC 89
    hex output = 5B 01 66 69 6F 35 06 4F
    I can capture more samples if need be? Any help would be greatly appreciated as I've been trying to figure this out for a week and I'm stumped!

    Andrew



Look Here ->
  • #2
    Senior Member
    trash's Avatar
    Join Date
    Jan 2008
    Location
    Tamworth
    Posts
    4,088
    Thanks
    148
    Thanked 3,228 Times in 1,451 Posts
    Rep Power
    1287
    Reputation
    47654

    Default

    Ok, so I find it hard to ignore hard questions. I'm always prepared to try (and fail). In this case, DAMN ! My head really hurts now trying to understand the maths.

    The task is really simple to understand. You and wiki describe it well.

    I have the [plain text] the [cypher] and the <algorithm> but not the (key).

    Anyhow, I don't expect to come up with an answer. I'll continue to think about for a while and re-read it to see if I can understand it. Maybe even write some code.
    But don't hold your breath, I think I'm too stupid for this one

    The most obvious method to me is brute force. But 64 bits is going to take a while. About 30,000 years at 20 megaflops.
    It might be possible to search all known common polys, that should reduce it to a few million choices.

    I'll have another look at the source coding later tonight.
    Yes I am an agent of Satan, but my duties are largely ceremonial.

  • The Following User Says Thank You to trash For This Useful Post:

    Bigfella237 (14-11-16)

  • #3
    LSemmens
    lsemmens's Avatar
    Join Date
    Dec 2011
    Location
    Rural South OZ
    Posts
    10,573
    Thanks
    11,853
    Thanked 7,053 Times in 3,334 Posts
    Rep Power
    3149
    Reputation
    132432

    Default

    So? Whose bank are you trying to rob?
    I'm out of my mind, but feel free to leave a message...

  • #4
    Senior Member

    Join Date
    Apr 2012
    Location
    14 Wombat Cres, Goanna Heights NSW
    Posts
    1,403
    Thanks
    728
    Thanked 1,150 Times in 576 Posts
    Rep Power
    602
    Reputation
    20563

    Default

    Thanks trash, I feel a little less stupid now upon hearing that it has you stumped too!

    I originally thought along the same (brute-force) lines, but then I was reminded that LFSR is linear, not cryptographic.

    Quote Originally Posted by lsemmens View Post
    So? Whose bank are you trying to rob?
    "I could tell you, but then I'd have to kill you"

    Nah, LFSR is not really a security measure like that, it's simply a way to generate a predictable pseudo-random value that can be used to, for example, verify the integrity of data. At present I can read each LFSR value from this data, but I need to be able to verify the next iteration for myself, rather than just blindly accepting that it's correct.

    Andrew

  • #5
    Senior Member

    Join Date
    Apr 2012
    Location
    14 Wombat Cres, Goanna Heights NSW
    Posts
    1,403
    Thanks
    728
    Thanked 1,150 Times in 576 Posts
    Rep Power
    602
    Reputation
    20563

    Default

    Another appeal for help on this, in case anyone out there good at math missed this last time around, this still has me stumped!

    The problem (as set out above) is unchanged, but if it helps, I've captured five consecutive iterations of the polynomial (as below):

    Code:
    0x B8 7C 52 CC BB CB 65 B9 
    generates:
    0x 15 B4 5E 94 84 78 E9 23 
    generates:
    0x 6D 39 6C 8D 77 DC 9E 6C 
    generates:
    0x 4E 93 20 5D 04 60 73 08 
    generates:
    0x 5B C8 37 DF 18 93 72 BF 
    generates:
    0x 3E A3 58 A3 C9 88 85 22 
    and so on...
    I'm sure it can be done, I just need to find someone who can do it! If anyone could suggest someone I could contact, or contact them on my behalf, I would be eternally grateful.

    Thanks in advance!
    Andrew

  • Bookmarks

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •