Secure boot and firmware updates (OTA) in IOT Protocols - Time & Space Complexity

Time Complexity: Secure boot and firmware updates (OTA)

O(n)

Understanding Time Complexity

When devices update their firmware over the air, the time it takes depends on how the update process handles data and security checks.

We want to know how the time grows as the firmware size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Pseudocode for OTA firmware update with secure boot checks
function performFirmwareUpdate(firmwareData) {
  verifySignature(firmwareData.signature); // Check signature once
  for (chunk of firmwareData.chunks) {
    decrypt(chunk); // Decrypt each chunk
    writeToFlash(chunk); // Write chunk to device memory
  }
  rebootDevice(); // Restart device to apply update
}
    

This code verifies the firmware signature once, then processes each chunk by decrypting and writing it, before rebooting.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over firmware chunks to decrypt and write each one.
• How many times: Once for each chunk in the firmware data.

How Execution Grows With Input

The time to update grows as the number of chunks grows, since each chunk is handled one by one.

Input Size (n)	Approx. Operations
10 chunks	About 10 decrypt and write steps
100 chunks	About 100 decrypt and write steps
1000 chunks	About 1000 decrypt and write steps

Pattern observation: The work grows directly with the number of chunks, so doubling chunks doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the update time grows in a straight line with the firmware size.

Common Mistake

[X] Wrong: "The signature verification inside the loop makes the time grow faster than linearly."

[OK] Correct: The signature is checked only once before the loop, so it does not add repeated cost.

Interview Connect

Understanding how update time scales with firmware size shows you can reason about real device constraints and security steps clearly.

Self-Check

"What if the signature verification was done for each chunk instead of once? How would the time complexity change?"

Practice

1. What is the main purpose of secure boot in IoT devices?

easy

A. To ensure only trusted software runs on the device

B. To speed up the device startup time

C. To allow any software to run without restrictions

D. To backup device data automatically

Solution

1. Step 1: Understand secure boot concept

   Secure boot checks the software's authenticity before running it on the device.

2. Step 2: Identify the main goal

   The goal is to prevent untrusted or malicious software from running.

3. Final Answer:

   To ensure only trusted software runs on the device -> Option A

4. Quick Check:

   Secure boot = trusted software only [OK]

Hint: Secure boot means only trusted software runs [OK]

Common Mistakes:

• Thinking secure boot speeds startup
• Believing secure boot allows any software
• Confusing secure boot with data backup

2. Which of the following is the correct command to verify a firmware update signature using openssl?

easy

A. openssl verify -CAfile ca.pem firmware.sig

B. openssl sign -verify firmware.bin

C. openssl dgst -verify ca.pem -signature firmware.sig firmware.bin

D. openssl check firmware.sig firmware.bin

Solution

1. Step 1: Recall openssl dgst verify syntax

   The correct syntax to verify a signature is: openssl dgst -verify [pubkey/cert] -signature [signature] [file].

2. Step 2: Match the command with syntax

   openssl dgst -verify ca.pem -signature firmware.sig firmware.bin matches this syntax exactly for verifying firmware signature.

3. Final Answer:

   openssl dgst -verify ca.pem -signature firmware.sig firmware.bin -> Option C

4. Quick Check:

   Verify signature = openssl dgst -verify [key] -signature [sig] [file] [OK]

Hint: Verify signature uses 'dgst -verify' and '-signature' flags [OK]

Common Mistakes:

• Using 'openssl sign' instead of 'dgst'
• Missing '-verify' or '-signature' flags
• Using wrong command like 'openssl check'

3. Given this pseudo-code for OTA update verification:

if verify_signature(firmware, signature, public_key):
    install_firmware(firmware)
else:
    reject_update()

What happens if the signature does not match?

medium

A. Update is rejected and not installed

B. Signature is ignored and update proceeds

C. Device reboots automatically

D. Firmware is installed anyway

Solution

1. Step 1: Analyze the conditional logic

   If verify_signature returns false, the else branch runs.

2. Step 2: Understand else branch action

   The else branch calls reject_update(), meaning the update is not installed.

3. Final Answer:

   Update is rejected and not installed -> Option A

4. Quick Check:

   Signature mismatch = reject update [OK]

Hint: If signature fails, update is rejected [OK]

Common Mistakes:

• Assuming firmware installs despite bad signature
• Thinking device reboots automatically
• Ignoring signature verification result

4. You wrote this OTA update script snippet:

if verify_signature(firmware, signature, public_key):
    install_firmware(firmware)
else:
    install_firmware(firmware)

What is the main problem here?

medium

A. Firmware is never installed

B. Signature verification function is missing

C. Public key is not used in verification

D. Firmware is installed even if signature verification fails

Solution

1. Step 1: Review the else branch code

   Both if and else branches call install_firmware(firmware).

2. Step 2: Understand security impact

   This means firmware installs regardless of signature check, breaking security.

3. Final Answer:

   Firmware is installed even if signature verification fails -> Option D

4. Quick Check:

   Else installs firmware = security risk [OK]

Hint: Else should reject update, not install firmware [OK]

Common Mistakes:

• Ignoring else branch code
• Assuming verification function is missing
• Confusing public key usage

5. You want to implement a secure OTA update system that:
- Verifies firmware signature
- Supports rollback if update fails
- Uses secure boot to prevent unauthorized code

Which sequence of steps best achieves this?

hard

A. Enable secure boot -> Install firmware -> Verify signature -> Rollback if failure

B. Enable secure boot -> Verify signature -> Install firmware -> Rollback if failure

C. Verify signature -> Install firmware -> Enable secure boot -> Rollback if failure

D. Install firmware -> Verify signature -> Enable secure boot -> Rollback if failure

Solution

1. Step 1: Enable secure boot first

   Secure boot must be active to prevent unauthorized code from running at startup.

2. Step 2: Verify firmware signature before installing

   Check the update is trusted before installation to avoid bad firmware.

3. Step 3: Install firmware and support rollback

   Install only if verified, and rollback if update fails to keep device safe.

4. Final Answer:

   Enable secure boot -> Verify signature -> Install firmware -> Rollback if failure -> Option B

5. Quick Check:

   Secure boot first, verify, install, rollback [OK]

Hint: Enable secure boot first, then verify before install [OK]

Common Mistakes:

• Installing firmware before verifying signature
• Enabling secure boot after installation
• Skipping rollback support