Author Topic: Generating a UUID  (Read 12589 times)

0 Members and 1 Guest are viewing this topic.

Online HwAoRrDkTopic starter

  • Super Contributor
  • ***
  • Posts: 1936
  • Country: gb
Generating a UUID
« on: November 21, 2023, 08:20:19 pm »
I have a need to generate an RFC 4122-compliant UUID on a microcontroller. Its purpose is to be presented to a master system that talks to the MCU to identify each instance of add-on board (kind of like a serial number, but globally unique). I believe this is primarily so that the system can identify when more than one instance of the same board (i.e. with identical product and vendor IDs) is present, but I don't think it does anything else with the UUID.

However, I'm not sure how I can construct such a UUID given the limited facilities available to me.

For a start, I don't have any time-keeping available (only a millisecond timestamp since power-on), so I can't create a Version 1 UUID that is based on a UTC timestamp ("the current time as a 60-bit count of 100-nanosecond intervals since 00:00:00.00, 15 October 1582"). What I do have available is a 64-bit unique ID from the MCU that is (or should be!) distinct for each chip. (Or is it 96-bit? The chip has three 32-bit registers containing the unique ID, but perhaps one is a non-unique value.)

A Version 4 random UUID isn't suitable, because that would change every time, and this UUID is supposed to be persistently consistent for a given piece of hardware.

So I'm thinking that maybe I could construct a Version 3 or 5 "Named-based" UUID? But that involves hashing using MD5 or SHA-1, and I'm hesitant to implement that on a low-powered MCU.

Any suggestions?
 

Offline eutectique

  • Frequent Contributor
  • **
  • Posts: 638
  • Country: be
Re: Generating a UUID
« Reply #1 on: November 21, 2023, 10:10:43 pm »
I have a need to generate an RFC 4122-compliant UUID on a microcontroller.

Strange requirement.

If you strictly need to generate it on the µC, you can use chip ID as a random number. Consult the relevant chapter of the data sheet about its length.

Can you read the chip ID at production time, generate UUID with uuidgen utility, and write it to the µC?
 

Offline zilp

  • Frequent Contributor
  • **
  • Posts: 351
  • Country: de
Re: Generating a UUID
« Reply #2 on: November 21, 2023, 10:14:45 pm »
So I'm thinking that maybe I could construct a Version 3 or 5 "Named-based" UUID? But that involves hashing using MD5 or SHA-1, and I'm hesitant to implement that on a low-powered MCU.

"low-powered" as in?
 

Offline ejeffrey

  • Super Contributor
  • ***
  • Posts: 4865
  • Country: us
Re: Generating a UUID
« Reply #3 on: November 21, 2023, 10:20:55 pm »
The UUID is assigned once and stays constant forever? Do you have NVRAM to store it or does it need to be derived from the hardware?

If you have NVRAM to store it and you have a programming / test phase of production can you just generate the UUID on the programming host and write it at that time? Alternately does you microcontroller have a built in hardware unique ID?  If so, pre-generate the high bits once using whatever chosen method you like then fill in the low bits with the hardware ID.
 

Offline SiliconWizard

  • Super Contributor
  • ***
  • Posts: 17840
  • Country: fr
Re: Generating a UUID
« Reply #4 on: November 21, 2023, 10:23:06 pm »
If you need a UUID with 128 bits and you have less than this available on your chip, I'm not sure how you can do that reliably.
You can always do some twiddling on the 64- or 96-bit unique ID of your MCU to generate a 128-bit value, but this will never be guaranteed to be really unique. Maybe it can be made "good enough" for your purpose.

One simple, if maybe less practical solution from a production POV (if you have to mass-produce this), is just to generate UUIDs at production time on a computer and flash them on each MCU. Problem solved.
 

Offline zilp

  • Frequent Contributor
  • **
  • Posts: 351
  • Country: de
Re: Generating a UUID
« Reply #5 on: November 21, 2023, 10:35:30 pm »
If you need a UUID with 128 bits and you have less than this available on your chip, I'm not sure how you can do that reliably.
You can always do some twiddling on the 64- or 96-bit unique ID of your MCU to generate a 128-bit value, but this will never be guaranteed to be really unique.

Well, technically true--but if you use a cryptographic hash function, the collision probability introduced by the hashing is negligible.
 

Offline nctnico

  • Super Contributor
  • ***
  • Posts: 30413
  • Country: nl
    • NCT Developments
Re: Generating a UUID
« Reply #6 on: November 21, 2023, 11:14:32 pm »
If you need a UUID with 128 bits and you have less than this available on your chip, I'm not sure how you can do that reliably.
You can always do some twiddling on the 64- or 96-bit unique ID of your MCU to generate a 128-bit value, but this will never be guaranteed to be really unique.

Well, technically true--but if you use a cryptographic hash function, the collision probability introduced by the hashing is negligible.
That depends on the length of the input. If your input is 1 bit, then you'll only get 2 possible hashes. The simplest thing to do is to repeat the chip's ID until the length requirement of the UUID is satisfied.

BTW: I don't feel comfortable at all with generating 'unique' identifiers using some kind of randomizer. A serial number from a chip which is incremental will be unique for sure. A random generated ID will have duplicates. Murphy's law will make sure of that. I'd only use a random number if there is no other option at all.
There are small lies, big lies and then there is what is on the screen of your oscilloscope.
 

Online HwAoRrDkTopic starter

  • Super Contributor
  • ***
  • Posts: 1936
  • Country: gb
Re: Generating a UUID
« Reply #7 on: November 21, 2023, 11:27:18 pm »
Well, it's a pretty moot point regardless of whether or not I have the CPU horsepower to calculate a MD5/SHA-1 hash with the MCU in a reasonable amount of time. I just grabbed a public domain MD5 implementation and compiled it in, and it's ballooned my firmware size way over the amount of flash space available. So constructing a Version 3 name-based UUID on-device is out. :--

I was really hoping to have a common firmware image that can be just programmed as-is onto every device, hence why I was hoping to take advantage of the MCU's unique hardware ID.

If I wanted to generate the UUID at programming time based on the chip's hardware ID, I would have to re-compile the firmware for each and every device, because I don't have any NVRAM (e.g. EEPROM) to store it separately. I would really rather avoid a distinct firmware image per-device.

I wonder if perhaps I could do the following:

- Generate a single 'master' Version 1 time-based UUID.
- Include that in my firmware.
- On-demand, substitute the most-significant 48 bits (the 'node' field) with part of the MCU's hardware ID.

I mean, the MCU's hardware ID isn't too different from a MAC address (what conventionally goes in the 'node' field), is it? I would just need to determine what part of the chip's 64-bit (or 96-bit? - TBD) hardware is suitable for truncation to 48 bits. If the manufacturer bases the hardware ID on a serial number, then I suppose there may be certain bits of the ID that are more likely not to change from chip to chip.
 

Online dobsonr741

  • Frequent Contributor
  • **
  • Posts: 979
  • Country: us
Re: Generating a UUID
« Reply #8 on: November 21, 2023, 11:41:55 pm »
I do not see why would you need unique firmware for each device, or customize the FW image. Try to externalize and generate one externally and program in EEPROM or a region of the Flash at MCU programming time. Is the device SWD capable?

If you need dynamically regenerated UUIDs, from time to time, and you have no timekeeping, even more so when you need cryptographically strong UUID, you need a crypto chip with TRNG in it. Not a big deal, such I2C devices costs <$1. And a UUID might not be secure - though not sure it is your case.
« Last Edit: November 21, 2023, 11:44:51 pm by dobsonr741 »
 

Offline eutectique

  • Frequent Contributor
  • **
  • Posts: 638
  • Country: be
Re: Generating a UUID
« Reply #9 on: November 22, 2023, 12:01:52 am »
If I wanted to generate the UUID at programming time based on the chip's hardware ID, I would have to re-compile the firmware for each and every device, because I don't have any NVRAM (e.g. EEPROM) to store it separately.

A decent toolchain would be capable of generating s-record files (or intel-hex, for that matter), combining two files together, and flashing them into the device. One file would be the firmware, another is the UUID for that specific device.

You said nothing about your MCU, but in an ARM cortex-m device you can reserve a place for the UUID just after the vector table and before your .text section, looking at the vast majority of linker scripts. You get the drift.
 

Offline ejeffrey

  • Super Contributor
  • ***
  • Posts: 4865
  • Country: us
Re: Generating a UUID
« Reply #10 on: November 22, 2023, 12:11:00 am »
If you need a UUID with 128 bits and you have less than this available on your chip, I'm not sure how you can do that reliably.
You can always do some twiddling on the 64- or 96-bit unique ID of your MCU to generate a 128-bit value, but this will never be guaranteed to be really unique. Maybe it can be made "good enough" for your purpose.

Well it's enough to guarantee uniqueness within the context of instances of your device. At least as long as you trust your MCU vendor. Which is probably good enough but if you want global uniqueness do this:

1) Generate a single UUID on your development workstation now, using whatever technique you prefer.
2) compile that into your source code as the UUID template
3) the UUID is the XOR of the template with the MCU hardware ID
4) if you ever move to a different MCU vendor or change the hardware where there is a possibility for collision in the hardware unique ID, regenerate the template.

 

Offline rteodor

  • Frequent Contributor
  • **
  • Posts: 514
  • Country: ro
Re: Generating a UUID
« Reply #11 on: November 22, 2023, 04:14:17 am »
If I wanted to generate the UUID at programming time based on the chip's hardware ID, I would have to re-compile the firmware for each and every device, because I don't have any NVRAM (e.g. EEPROM) to store it separately.

A decent toolchain would be capable of generating s-record files (or intel-hex, for that matter), combining two files together, and flashing them into the device. One file would be the firmware, another is the UUID for that specific device.

You said nothing about your MCU, but in an ARM cortex-m device you can reserve a place for the UUID just after the vector table and before your .text section, looking at the vast majority of linker scripts. You get the drift.

Just set the linker script to reserve space for UUID. Then depending on tools available either patch the image before flashing or do it in two steps: flash once with the same image then set UUID either in another flashing run or via an interface like UART, CAN, Ethernet.
 
The following users thanked this post: SiliconWizard

Offline SiliconWizard

  • Super Contributor
  • ***
  • Posts: 17840
  • Country: fr
Re: Generating a UUID
« Reply #12 on: November 22, 2023, 07:14:21 am »
Well, it's a pretty moot point regardless of whether or not I have the CPU horsepower to calculate a MD5/SHA-1 hash with the MCU in a reasonable amount of time. I just grabbed a public domain MD5 implementation and compiled it in, and it's ballooned my firmware size way over the amount of flash space available. So constructing a Version 3 name-based UUID on-device is out. :--

Yes, but unless you envision to make billions of devices and need to ensure a collision probability < 10e-12 among all of them, you probably don't need to resort to such a big weapon.
For instance, to generate reasonable 32-bit and 64-bit UIDs (that I never claimed to be standard UUIDs of course) from more data bits, locally on MCUs, I've used Fletcher checksums successfully. Very lightweight, simple and fast. While having some known flaws, that would qualify as "good enough" for a lot of practical applications. Now if you must comply with some standard, of course, forget about that and use the big weapons.

I was really hoping to have a common firmware image that can be just programmed as-is onto every device, hence why I was hoping to take advantage of the MCU's unique hardware ID.

As several have already suggested, this can easily be done without having to modify the firmware itself. You can flash the UUID (along with other production data if needed) separately using the same tools.
 

Offline Siwastaja

  • Super Contributor
  • ***
  • Posts: 11440
  • Country: fi
Re: Generating a UUID
« Reply #13 on: November 22, 2023, 08:28:42 am »
BTW: I don't feel comfortable at all with generating 'unique' identifiers using some kind of randomizer. A serial number from a chip which is incremental will be unique for sure. A random generated ID will have duplicates.

There is no fundamental problem; length of the random ID just has to be long enough. FYI, I have bad news for you: the whole microcontroller is designed to fail randomly through metastability of flip-flops; RAM fails randomly, even ECC RAM fails randomly. It's just designed to fail rarely enough. You can do the same analysis for a random ID, and it is much easier to do so, even on a napkin (unlike RAM corruption modeling which requires quite deep semiconductor understanding.)

The benefit of randomly generated ID is that it does not need central registration, which in some cases can become a daunting task, and has also surface area for bugs.

A serial number from a chip which is incremental will be unique for sure.

Incremental ID won't be unique "for sure" if there is a race condition bug in assignment. Or any other bug. Or RAM corruption on the incremental counter, which has similar order of magnitude of probability than generating e.g. random 256-bit identifiers to begin with.

UUID is of course more complex than just random alone, utilizing the concept of having synchronized clocks all over the planet (or universe, as they market it). Whether this helps or hinders depend on application.
« Last Edit: November 22, 2023, 08:31:16 am by Siwastaja »
 

Online HwAoRrDkTopic starter

  • Super Contributor
  • ***
  • Posts: 1936
  • Country: gb
Re: Generating a UUID
« Reply #14 on: November 24, 2023, 05:32:43 am »
If I wanted to set the UUID value in an otherwise-generic firmware post-build, does this sound like a decent strategy?

1. Declare a variable in my source code for it, placing it in a special section, e.g.: static const uint8_t my_uuid[16] __attribute__((section(".my_uuid"), used, retain))
2. At some point post-build:
    a) Generate the per-unit UUID via whatever means (random, based on chip hardware ID, etc), put the 128-bit raw binary value in a file.
    b) With objcopy, make a unit-specific copy of the firmware, substituting the UUID value into the special section, e.g.: objcopy -O ihex --update-section .my_uuid=generated_uuid.bin firmware.elf firmware_with_uuid.hex

It seems I need the 'used' and 'retain' attributes to stop the linker garbage-collecting the section because nothing apparently references it. But that doesn't make sense to me because obviously other code references the variable. :-//

Should I be putting anything in my linker script for this new section? That is, regarding placement or ordering, or otherwise. Right now it seems to be placing the section after .rodata.*, which I think is a suitable place, but I can't help but feel that's by coincidence, rather than design. Perhaps adding the section to the linker script would avoid the need for the attributes mentioned above?
 

Offline rteodor

  • Frequent Contributor
  • **
  • Posts: 514
  • Country: ro
Re: Generating a UUID
« Reply #15 on: November 24, 2023, 07:08:23 am »
First of all you did not tell what controller and what compiler you are using. Both the controller and the compiler have specific ways regarding self-flashing.
Your mention of '.rodata' section hints at GCC.

Should I be putting anything in my linker script for this new section? That is, regarding placement or ordering, or otherwise. Right now it seems to be placing the section after .rodata.*, which I think is a suitable place, but I can't help but feel that's by coincidence, rather than design. Perhaps adding the section to the linker script would avoid the need for the attributes mentioned above?

Yes this is very recommended to declare a dedicated section in the linker script. Just like with serial numbers.
And it is preferably to put this section away from the rest of the code at a well defined address (towards end of flash for example) and there are reasons for that:
  • 1. flash block size: flashing is usually done at a flash erase block size (which might or might not be the same as flash write size). If this dedicated section is placed in the vicinity to other used data/code, then that data/code needs to be copied too before erasing and writing back the block. Software can do that yes, but it shouldn't.
  • 2. block alignment: leaving the linker to place the section you might find that the section overlaps over two block sizes. The software can manage this too but it is just much simpler to tell the linker what you want. Every compiler I used had linker commands to allocate a section to a well determined place.
  • 3. flash access size: some controllers might have larger access size and caching, for example: the flash is accessed (internally in the MCU) in 128 bytes chunks and if you change data in flash the data in cache has to be updated too. Otherwise if the controller runs code from the immediate vicinity of the updated flash area it my crash. This is valid usually for larger controllers/SoC's and it is very specific. In the example above a 128 bytes section could be reserved entirely even if only 5 bytes are used.

 

Online HwAoRrDkTopic starter

  • Super Contributor
  • ***
  • Posts: 1936
  • Country: gb
Re: Generating a UUID
« Reply #16 on: November 24, 2023, 07:36:14 am »
Both the controller and the compiler have specific ways regarding self-flashing.

Huh? ??? Who said anything about self-flashing? That's not what I'm doing here.

And I'm not proposing in my previous post to update the UUID location in flash with a second programming operation, after the main firmware flashing. No, I'm talking about substituting parts of the firmware image before flashing.
 

Offline rteodor

  • Frequent Contributor
  • **
  • Posts: 514
  • Country: ro
Re: Generating a UUID
« Reply #17 on: November 24, 2023, 08:26:28 am »
Both the controller and the compiler have specific ways regarding self-flashing.

Huh? ??? Who said anything about self-flashing? That's not what I'm doing here.

And I'm not proposing in my previous post to update the UUID location in flash with a second programming operation, after the main firmware flashing. No, I'm talking about substituting parts of the firmware image before flashing.

Uh, it seems that my morning didn't start :) And I have to run already...

Never tried this updating of elf file but I don't see why it should not work.

 

Offline Siwastaja

  • Super Contributor
  • ***
  • Posts: 11440
  • Country: fi
Re: Generating a UUID
« Reply #18 on: November 24, 2023, 08:30:07 am »
Most MCUs have special places in flash which are not erased through the normal chip erase command, but by a different command. For example, in STM32, it's called User Option Bytes IIRC, see the manual. These flash regions are the perfect place to store things like factory-generated unique IDs, because when you develop your stuff, you don't wipe it by accident as easily, but if you so wish, you can always update it.
 
The following users thanked this post: rteodor

Offline abyrvalg

  • Frequent Contributor
  • **
  • Posts: 898
  • Country: es
Re: Generating a UUID
« Reply #19 on: November 24, 2023, 02:25:07 pm »
If your programmer tool support hex files, instead of linking/objcopying an UUID into ELF you can also write it into a separate hex file and either load two files into the programmer tool or merge them into single file (there are tools like mergehex or hexmerge), or code some script generating an UUID and adding it straight into the fw.hex (that would be few lines in Python).

But what degree of uniqueness you actually need? If the requirement is just “all my boards must have different UUIDs” then using the mentioned 96-bit CPU ID extended to 128 bits with a fixed part would be just fine.
 

Offline abyrvalg

  • Frequent Contributor
  • **
  • Posts: 898
  • Country: es
Re: Generating a UUID
« Reply #20 on: November 24, 2023, 02:46:11 pm »
A Python tool:
Code: [Select]
#!/usr/bin/env python3

# requires intelhex package: pip install intelhex

# fash address where to place the UUID
UUID_ADDR = 0x3FF00

from sys  import argv, exit
if len(argv)!=2:
exit("Usage: "+argv[0]+" <fw.hex>")

import uuid
import intelhex

fw = intelhex.IntelHex(argv[1])

new_uuid = uuid.uuid1() # RFC4122v1
fw.puts(UUID_ADDR, new_uuid.bytes)

fw.write_hex_file(argv[1])
 
The following users thanked this post: Siwastaja, HwAoRrDk

Offline mikeselectricstuff

  • Super Contributor
  • ***
  • Posts: 14847
  • Country: gb
    • Mike's Electric Stuff
Re: Generating a UUID
« Reply #21 on: November 24, 2023, 02:48:11 pm »
If the purpose is unique serialisation, as opposed to cryptographic, then you probably don't need all that many bits.

A method I use to generate ethernet MACs is to run a 32 bit timer at the system clock rate (50Mhz), and on the first human interaction ( e.g. dip switch change) seen after the first-ever powerup for the factory test, capture the timer value and write to a dedicated location at the end of the internal flash as the serial number.



 
Youtube channel:Taking wierd stuff apart. Very apart.
Mike's Electric Stuff: High voltage, vintage electronics etc.
Day Job: Mostly LEDs
 

Offline mikeselectricstuff

  • Super Contributor
  • ***
  • Posts: 14847
  • Country: gb
    • Mike's Electric Stuff
Re: Generating a UUID
« Reply #22 on: November 24, 2023, 02:49:17 pm »
BTW you can also buy I2C EEPROMS preprogrammed with globally unique IDs ( and a registered ethernet MAC prefix), from Microchip
 
Youtube channel:Taking wierd stuff apart. Very apart.
Mike's Electric Stuff: High voltage, vintage electronics etc.
Day Job: Mostly LEDs
 

Offline nctnico

  • Super Contributor
  • ***
  • Posts: 30413
  • Country: nl
    • NCT Developments
Re: Generating a UUID
« Reply #23 on: November 24, 2023, 03:02:56 pm »
BTW you can also buy I2C EEPROMS preprogrammed with globally unique IDs ( and a registered ethernet MAC prefix), from Microchip
Those are a good option as well. I use these in several of my designs. They are a very cost effective solution.
There are small lies, big lies and then there is what is on the screen of your oscilloscope.
 

Offline peter-h

  • Super Contributor
  • ***
  • Posts: 6127
  • Country: gb
  • Doing electronics since the 1960s...
Re: Generating a UUID
« Reply #24 on: November 24, 2023, 04:13:50 pm »
What is this UUID for?
Z80 Z180 Z280 Z8 S8 8031 8051 H8/300 H8/500 80x86 90S1200 32F417
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf

 

- - -
-->