3
$\begingroup$

The Gameboy Advance encrypts data sent over its serial port. It assembles a random number to seed a linear congruential generator. Then, it xors this PRN, the data, a symmetric key, and the byte offset from the file.

Is there a rationale for this? The receiver must know the byte address, because it needed to know how many times to iterate the LCG.

(See here for a description of the algorithm.)

I'm trying to determine whether the algorithm is a stream cipher or some version of a block cipher in CTR mode.

$\endgroup$
  • $\begingroup$ Is there a rationale for this? I'm only speculating, but it sounds like an attempt to frustrate homebrewing. $\endgroup$ – Justin Lardinois Dec 21 '17 at 23:38
  • $\begingroup$ @JustinLardinois It's not uncommon for data buses to use an LFSR for "scrambling" to reduce di/dt (electrical interference). I sort of doubt the GBA's serial connection was fast enough to need that, though. $\endgroup$ – forest Aug 28 at 8:09
4
$\begingroup$

Quoting the linked source:

 if normal_mode    then c=C387h:x=C37Bh:k=43202F2Fh
 if multiplay_mode then c=FFF8h:x=A517h:k=6465646Fh
 m=dword(pp,cc,cc,cc):f=dword(hh,rr,rr,rr)
 for ptr=000000C0h to (file_size-4) step 4
   c=c xor data[ptr]:for i=1 to 32:c=c shr 1:if carry then c=c xor x:next
   m=(6F646573h*m)+1
   send_32_or_2x16 (data[ptr] xor (-2000000h-ptr) xor m xor k)
 next
c=c xor f:for i=1 to 32:c=c shr 1:if carry then c=c xor x:next
wait_all_units_ready_for_checksum:send_32_or_1x16 (c)

 pp    palette_data
 cc    random client_data[1..3] from slave 1-3, FFh if slave not exists
 hh    handshake_data, 11h+client_data[1]+client_data[2]+client_data[3]

I read the question as asking the role of xor (-2000000h-ptr).

It ads a small layer of security by obscurity, but does not strengthen the algorithm from a cryptographic standpoint, since a passive eavesdropper can know ptr by merely counting the octets exchanged.

The algorithm is a stream cipher for encryption (with the keystream obtained as the XOR of a Linear Congruential Generator m, the aforementioned (-2000000h-ptr), and key k); and a MAC for integrity (using a Cyclic Redundancy Check c with feedback polynomial defined by x). The whole thing is more security by obscurity than real crypto.

Update: The ptr term can not be naturally considered as the counter of the CTR mode of operation. For this we would need chunks of the keystream to be expressable as a function of key and counter, without other internal state evolving sequentially. Here we have other such internal state m. Otherwise said, it is easy to convert a cipher operating in CTR mode for direct access, when here the iterated LCG makes that uneasy. I see no natural way to consider this as a block cipher in any mode.

On the other hand, if we really wanted that, it is possible to express the state of the LCG m as a function F of the current value of ptr and the initial m0=dword(pp,cc,cc,cc), and then the keystream becomes (-2000000h-ptr) xor F(ptr,m0) xor k, or $E_{(\mathtt{m_0},\mathtt{k})}(\mathtt{ptr})$, and we have a CTR mode with a block cipher $E$, having extremely weak diffusion of its plaintext input. That would be grossly inefficient if we implemented F iteratively, but there are ways around.

$\endgroup$
  • $\begingroup$ Putting its cryptographic deficiencies aside, the byte offset provides a counter and a block width. Would it be coherent to interpret this as a block cipher in CTR mode? The implementations of this I've found online are mostly just for-loops and hard-coded values, so I'd like to frame my implementation in actual cryptographic concepts, if at all possible. For example, LCGs are inadequate as PRNGs in cryptographic schemes, but that is the purpose it is serving (however inadequately). $\endgroup$ – Brian Graham Dec 20 '17 at 17:45
  • $\begingroup$ @BrianGraham: see update. $\endgroup$ – fgrieu Dec 20 '17 at 18:16
  • $\begingroup$ What a clear and concise explanation - very much appreciated. $\endgroup$ – Brian Graham Dec 20 '17 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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