8
$\begingroup$

The 6502 is the CPU in a Tamagotchi (which can be hacked to run custom code). SHA-1 is the default hash used for TOTP (the algorithm used by two-factor authentication tokens and apps). Hopefully you now understand why I'm asking this.

(given this context, this would be a couple dozen bytes of input, and less than a second or so of time)

$\endgroup$
6
  • 1
    $\begingroup$ And why the emphasis on safely? What are you getting at (other than hash rate)? $\endgroup$
    – Paul Uszak
    Aug 14, 2018 at 23:53
  • 1
    $\begingroup$ Define "a reasonable length of time". Is that some small number of nanoseconds, milliseconds, seconds, fortnights. And, how much data are we talking about hashing? A few bytes? A few terabytes? $\endgroup$
    – poncho
    Aug 15, 2018 at 0:52
  • $\begingroup$ edit: clarified @poncho's questions $\endgroup$
    – user371366
    Aug 15, 2018 at 2:56
  • $\begingroup$ @PaulUszak by "safety" i mean, not (easily) susceptible to power/timing analysis, which may rule out shortcuts that would make this computation cheaper. $\endgroup$
    – user371366
    Aug 15, 2018 at 3:13
  • $\begingroup$ I implemented few years ago a SHA1 on a CPU with a very similar instruction set as the 6502 (in assembler). Without any countermeasures against side channel attacks one round of SHA1 took about 60000 cycles. $\endgroup$
    – j.p.
    Aug 15, 2018 at 6:20

4 Answers 4

10
$\begingroup$

Yes, a 6502 can compute SHA-1 in a reasonable time: less than $\lceil(k+9)/64\rceil/5$ second for a $k$-byte message on a 1 MHz 6502 as on the 1977 Apple ][. E.g. 0.2s for up to 55 bytes. We need like 128 bytes of RAM excluding the hashed message. Code likely fits 1 kbyte of code including constants.

Note: I do not know clock speed, RAM and code size resources on a Tamagoshi.

I'm basing this on a commercial implementation I wrote for the 8031/8051, another 8-bit CPU (from an old post). My 660-byte code (including tables and C interface) is well below 50,000 CPU cycles per 64-byte block (where many instructions on registers are 1 cycle, and external memory access is 2 cycles; one cycle lasts 12 external clock periods of the original 8051, common variants reduce that to 6 or less). That code is not optimized quite to the max for speed, because the customer was short on easily addressable internal RAM, and code size was a consideration too. On the 6502, I estimate the number of CPU cycles would be less than 4 times that with unrolled code using zero-page addressing, that is less than 200,000 cycles. I would not be surprised if things could be brought down to 120,000 cycles or so. I second Poncho's comment that 83,700 cycles seems rather optimistic.

The most natural code is constant-time, thus at least a side-channel by timing is easy to avoid. Probing, and power/electromagnetic emission analysis are credible security threats, if an adversary can approach the hardware.

Note: I know no security CPU that used the 6502, but many have used the 6805 or derivatives, which are very comparable 8-bit CPUs. Some are still in active use.


Update: this answer reports a 6502 SHA-256 implementation that hashes at approx. 410 bytes/s on Commodore 64 (1 MHz). That translates to 64×1000000/410 ≈ 155,000 cycles per hash (for up to 55 bytes hashed). I think SHA-1 can be faster by a factor sizably less than two (the 80 rounds in SHA-1 rather than 64 in SHA-256 offsets much of the gain from the simpler rounds). This is consistent with the above estimates.

$\endgroup$
4
$\begingroup$

Here is my implementation of SHA-256 for the 6502. It has not been extensively checked for safety, but should be immune to timing attacks. It hashes at approx. 350 bytes/s on Commodore 64 (1 MHz). SHA-1 could be derived from this code rather easily (and would be faster, too).

https://github.com/laubzega/sha256_6502/

UPDATE: with some tweaks here and there it now runs at ~410 bytes/s.

$\endgroup$
5
  • 2
    $\begingroup$ Looking at the code, the most significant optimization I see remains possible is rewriting rol1…rol3 and ror1…ror3 using 4 precomputed tables each 256 bytes (page-aligned to avoid timing dependencies) holding at offset i the quantities (i<<3)&255, i>>5, i>>3, (i<<5)&255. Also these routines operate on a freshly shuffled argument, and that copy can be merged in (at the expense of code size). $\endgroup$
    – fgrieu
    Dec 5, 2022 at 5:53
  • 1
    $\begingroup$ @fgrieu Can you please share more details on this scheme? I can see how tables could potentially help with rol3/ror3 where it's enough to beat 90 cycles to be faster, but for rol[12]/ror[12] doing lookups, ORing and storing for all bytes within 30-60 cycles seems unlikely. That is, unless I misunderstood the role of the tables. $\endgroup$ Dec 5, 2022 at 17:43
  • $\begingroup$ @Miloslaw Smyk: I had misunderstood what ror1 ror2 rol1 rol2 do. My idea applies to ror3 and rol3 only, and you got that part. I agree that ror1 rol1 ror2 rol2 can't be improved the way I tell, at least for a local rewrite. More sizable gain for rol3 ror3 will come if we merge the preliminary copy, the table lookups, and the combination with the output; and then perhaps shift-by-two tables (consuming another 1kiB) could help for ror2 rol2, but at best marginally. $\endgroup$
    – fgrieu
    Dec 5, 2022 at 17:53
  • 1
    $\begingroup$ Tables decrease rol3/ror3 cycle count from 90 to 68. Not sure yet how to merge them with the preliminary copy without stomping over itself (or making an extra copy that defeats the purpose). I redid the measurements with VIC display fetches turned off, no visual feedback, and end time captured before (slow) printf. It's 402 b/s without tables and 410 b/s with them. I will push my changes later today. $\endgroup$ Dec 5, 2022 at 20:48
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – fgrieu
    Dec 6, 2022 at 7:05
3
$\begingroup$

SHA-1 on a 90MHz Pentium cpu from the same year the Tamagotchi was released takes 837 cycles to complete, assume it would take 8x on a 6502 because of the difference in instruction width and instructions per cycle (I could be way off, so I will use 10X as a baseline here).

8370 cycles at 1MHz is just under 100th of a second. Even if it was several times slower than that because if the speed of memory addressing and the memory used for input expansion, it should still be under 1s. My hybrid TOTP generates a new code every 86.4s (1000 times per day), which gives enough time to enter and authenticate the code, so I would say the 6502 would be indeed able to produce an HMAC-SHA-1 hash from a single iteration input (time code), and format a truncated value for a user in a reasonable length of time.

more details

It appears the CPU on a Tama-Go (more recent unit) is actually running at 8MHz, and is integrated into the display controller. It has 1536B of RAM and 320K of ROM, which should be more than enough to compute hash values.

Based on Poncho's comment, I looked up the instruction latencies for the 6502, they are around 6 cycles in the worst case, vs the pentium which is less than 1 (1469 instructions in 837 cycles) on average. If my 10x guess was accurate (it is not) that would mean 88ms for a hash iteration at 1MHz.

However, it appears the 6502 does not have variable bit rotations and shifts, it is 1 at a time, so my 10x guess is probably 20x off, although at 8MHz, that is still 1 HMAC-SHA-1 iteration in half a second.

If you want to try your hand at it, there is a web based simulator for the Tama-go, and you can find out for yourself how much code and cpu cycles are required to do the job.

$\endgroup$
4
  • 1
    $\begingroup$ PS. I would recommend a custom shielded case if you try this, I would think you could pick up the emanations from a calculations with a simple radio receiver $\endgroup$ Aug 15, 2018 at 1:58
  • 4
    $\begingroup$ You are way off with estimating 8x; a Pentium is a 32 bit CPU with multiple issue and plenty of registers; a 6502 is an 8 bit CPU, single issue (with each instruction taking multiple cycles), with hardly any registers (hence you'll spend quite of bit of time reading/writing temp contents to memory). 100x might be closer, but even that might not be achievable. On the other hand, doing a short hash once every 86.4 seconds should easily be achievable... $\endgroup$
    – poncho
    Aug 15, 2018 at 2:56
  • $\begingroup$ @RichieFrame unfortunately, last i checked the tamagotchi does not have any shielding built in... i expect my idea would not be very safe against any sort of hardware side-channels $\endgroup$
    – user371366
    Aug 15, 2018 at 3:11
  • $\begingroup$ @user371366 That shielding may not matter much. As most of the instructions are not data dependent (there are no switches depending on the data, which is a problem, e.g. when performing table access in "unprotected" AES). So you'd have to try and get to the data depending on listening to bit ops, which is very hard if the input changes all the time (as would be expected for a one-time-password protocol). $\endgroup$
    – Maarten Bodewes
    Dec 4, 2022 at 22:12
1
$\begingroup$

In this implementation of SHA-256 for the 6502 processor, a performance of 5.6 seconds per kB is mentioned or 178B/s. Now considering that SHA-256 is between 15-25% slower than SHA-1, you can safely assume around 4.5 seconds per kB or 222B/s.

$\endgroup$
3
  • $\begingroup$ Don't know where my previous comment went, but my PC can do SHA-1 hashes at 1 GB/s on a single core. We're clearly moved ahead. I presume you ran this at 1 MHz? Maybe a cycle count would otherwise be useful? A quick glance at Wikipedia shows this CPU being able to run from 1 MHz to 3 MHz, so that means that the numbers can be pretty far off depending on the situation. $\endgroup$
    – Maarten Bodewes
    Dec 6, 2022 at 14:22
  • 1
    $\begingroup$ Hey! To clarify, this isn't my code. I just did a bit of research and found it. I cannot reassure the measurements on which exactly cpu settings have been measured, but the git commit message says it was developed for C64. Also, since the measurements are for SHA-256 and not for SHA-1, I just applied my general knowledge to provide an estimate. I'm not sure how reliable my estimate is. $\endgroup$
    – tur11ng
    Dec 6, 2022 at 16:05
  • $\begingroup$ @MaartenBodewes: "my PC can do SHA-1 hashes at 1 GB/s on a single core. We're clearly moved ahead"; somewhat, however even back in 1997, the 6502 did not have cutting edge performance; instead, it was designed to be low cost (and performance wasn't that big of a deal, as long as it was "good enough"). $\endgroup$
    – poncho
    Dec 8, 2022 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.