Basic Encoding Rules

Basic Encoding Rules (abbreviazione BER) è un sistema di codifica composto da una serie di regole per la conversione di dati eterogenei in flussi di byte.

La codifica BER è strettamente legata allo standard ASN.1 ed è utilizzata per le comunicazioni SNMP e LDAP.

Il sistema di codifica è basato sul concetto di tripla <T,L,V> (Type o Tag, Length, Value) dove:

• Type o Tag : indica il tipo del dato codificato
• Length : indica la lunghezza in byte di "Value"
• Value : È il dato codificato vero e proprio

Quindi ad esempio per codificare il dato 7 come INTERO occorreranno 3 bytes:

• il primo che indica il Type (INTERO = 02₁₆);
• il secondo che indica la Length di v (in questo caso = 01₁₆).
• il terzo è la codifica del dato INTERO secondo le regole BER (in questo caso 07₁₆);

In definitiva INTEGER 7 in BER diviene 020107₁₆ dove si distinguono chiaramente T,L e V.

BER è strettamente legata ad ASN.1 soprattutto per quanto riguarda i tipi di dati. Come si può immaginare la codifica di V dipende dal tipo T. Ci sono alcuni tipi predefiniti in ASN.1 (si dice che sono Tag appartenenti alla Class UNIVERSAL). Per maggiori informazioni a tal proposito consultare OSS Nokalva - Books Overview.

In generale quando si deve effettuare la codifica BER di un dato si procede nel seguente modo:

1. si codifica T;
2. si codifica V;
3. dalla lunghezza di V si passa alla codifica di L.

Vediamo ora la codifica di ogni campo.

La codifica del campo T di solito chiede un unico Byte. La codifica dipende dai seguenti fattori:

• La classe di appartenenza del Tag
• Il tipo è PRIMITIVE o CONSTRUCTED
• L'identificativo del Tag nella classe di appartenenza

Se l'identificativo del tipo ${\displaystyle 0<=ID<=30}$ allora la codifica di T richiede un unico byte, altrimenti il numero di byte di T dipenderà dal valore di ID

Vediamo qui sotto come si presenta il primo byte di T:

La codifica di CLASS segue la seguente tabella:

 bit 7     bit 6         CLASS
 -----------------------------------
   0        0          UNIVERSAL
   0        1         APPLICATION
   1        0        context-specific
   1        1           PRIVATE

Il bit P\C = 0 indica che il tipo è PRIMITIVE (cioè è un tipo semplice come INTEGER o OID)

Il bit P\C = 1 indica che il tipo è CONSTRUCTED (cioè è un tipo composto da più tipi semplici come ad es. SEQUENCE)

I 5 bit di TAG invece:

• Contengono il valore binario di ID se ${\displaystyle 0<=ID<=30}$
• Contengono ${\displaystyle 11111_{2}}$ se ${\displaystyle ID>30}$

Nel primo caso, come è stato già detto, il T è composto da un unico byte. Nel secondo caso vanno invece codificati gli altri bytes di T.

Per codificare gli altri byte si procede nel seguente modo:

1. si converte l'ID in binario
2. si aggiunge un 1 ogni 7 bit
3. si completa il byte con un 0 in testa

NB !!! appena corretto!!! l'ultimo byte che compone l'ID viene composto con uno '0' in testa, proprio per indicare che l'ID finisce con quel byte.

Ad es. se ID = 250 in base 10, allora:

1. ${\displaystyle 250_{10}=FA_{16}=11111010_{2}}$
2. ${\displaystyle 11111010->1{\textbf {1}}1111010}$
3. ${\displaystyle 1{\textbf {1}}1111010->{\textbf {1}}0000001~{\textbf {0}}1111010}$

In definitiva ID = 250 viene codificato con ${\displaystyle 81FA_{16}}$

Codifica di INTEGER. Questo è di classe UNIVERSAL ed è PRIMITIVE. Il suo ID nella classe UNIVERSAL è 2.

${\displaystyle ID<=30}$ e quindi basterà 1 solo byte per T

Quindi:

CLASS = 00

P\C = 0

Tag = 00010

da cui se segue:

${\displaystyle T=02_{16}}$

Supponiamo di voler codificare un tipo PRIVATE e PRIMITIVE con ${\displaystyle ID=250_{10}}$

${\displaystyle ID>30}$ e quindi serviranno più byte per T

Primo byte:

CLASS = 11

P\C = 0

Tag = 11111 --> ${\displaystyle primobyte=11011111_{2}=DF_{16}}$

Altri byte (come abbiamo visto in precedenza) sono pari a ${\displaystyle 81FA_{16}}$ perché ${\displaystyle ID=250_{10}}$

In definitiva in questo caso ${\displaystyle T=DF81FA_{16}}$ ed è di 3 byte.

In questa sezione si indica con Len(V) il numero di byte di V.

La codifica di L è strettamente legata alla lunghezza del dato codificato V. Se si conosce a priori Len(V) allora si procede con la codifica definite length, altrimenti si applica la codifica indefinite length. La prima tecnica è preferibile in quanto permette un Decoding più semplice.

In questo tipo di encoding si distinguono 2 casi distinti:

1. se ${\displaystyle Len(V)<=127}$ allora L viene codificato in 1 byte (short definite form)
2. se ${\displaystyle Len(V)>127}$ allora L viene codificato in più byte (long definite form)

Questo è il caso più semplice. V è codificato in meno di 127 bytes ed L contiene esclusivamente il valore di Len(V) in esadecimale.

Il limite di 127 byte è dato dal fatto che 127 è 7F in esadecimale (01111111 in binario) e quindi il primo bit di L è sicuramente zero.

Ciò è utile in fase di Decoding, infatti se il primo bit è zero, significa che è stata usata la codifica di L su un solo byte.

In questo caso si procede nel seguente modo:

1. si codifica in binario Len(V)
2. si calcola ${\displaystyle Len(Len(V))}$, cioè la lunghezza in bytes di Len(V)
3. si pone nel primo byte di L = ${\displaystyle Len(Len(V))+80_{16}}$
4. si pone nei bytes seguenti Len(V)

La formula del punto 3 ha la seguente giustificazione:

• aggiungendo ${\displaystyle 80_{16}}$ si obbliga l'ultimo bit del primo byte di L ad essere 1.
• nei primi 7 bit del primo byte di L c'è in realtà la lunghezza dei byte restanti di L, infatti ${\displaystyle Len(Len(V))+1}$ indica proprio la lunghezza di L

In fase di Decoding per capire che stiamo usando una codifica di L su più byte di tipo long definite form deve quindi essere:

• il primo bit del primo byte di L= 1
• gli altri 7 bit del primo byte devono essere diversi da ${\displaystyle 0000000_{2}}$

V è codificato su 120 bytes.

Poiché ${\displaystyle 120<127}$ deve essere quindi usata la short definite form

In definitiva:${\displaystyle L=78_{16}}$

V è codificato su 1000 bytes.

Poiché ${\displaystyle 1000_{10}>127_{10}}$ deve essere quindi usata la long definite form.

Quindi:

1. ${\displaystyle Len(V)=1000_{10}=3E8_{16}=03E8_{16}}$
2. ${\displaystyle Len(Len(V))=2_{10}=02_{16}}$
3. byte 1 di L ${\displaystyle =Len(Len(V))+80_{16}=82_{16}=10000010_{2}}$
4. bytes 2,3 di L ${\displaystyle =Len(V)=03E8_{16}}$

In definitiva:${\displaystyle L=8203E8_{16}}$ ed è di ${\displaystyle Len(Len(V))+1=2+1=3bytes}$

Questo tipo ti encoding è usato quando non si conosce la Len(V) a priori.

In questo caso si procede con i seguenti passi:

• si pone ${\displaystyle L=10000000_{2}=80_{16}}$
• si aggiunge V
• in coda a V si aggiungono 2 bytes di zeri ${\displaystyle 0000_{16}}$

La codifica di V, come è stato più volte detto, dipende dal tipo T e dalla sua definizione tramite sintassi ASN.1 In questa sede sarà illustrata la codifica dei 3 tipi principali: INTEGER, OCTECT STRING e OBJECT ID. Per una panoramica completa di codifica decodifica si rimanda ancora a OSS Nokalva - Books Overview o OSS Nokalva - Books Overview

La codifica di un dato INTEGER dipende dal suo segno. Il primo bit del primo byte codificato è detto bit segno. Se questo è 0 allora il numero è positivo, altrimenti è negativo.

In questo caso la codifica è data dal valore binario del numero, a patto che si rispetti il bit segno, altrimenti bisogna aggiungere in testa un byte di zeri

Infatti se l'integer è ad es. ${\displaystyle 100_{10}}$ allora si ha: ${\displaystyle valore=100_{10}\to V=100_{10}=64_{16}=01100100_{2}}$. In questo caso il bit segno è zero e quindi la codifica è corretta.

Se invece l'integer è ad es. 250 allora si ha: ${\displaystyle V=250_{10}=FA_{16}=11111010_{2}}$. In questo caso il bit segno è 1 e quindi in fase di decodifica rappresenterebbe un numero negativo, vanno quindi aggiunti gli zeri in testa. In definitiva ${\displaystyle valore=250\to V=250_{10}=FA_{16}=00FA_{16}=0000000011111010_{2}}$. Come si può notare, aggiungendo gli zeri in testa il bit segno è correttamente zero.

Per gli integer negativi si utilizza il Complemento a due del valore. Ciò assicura che il bit segno è sempre negativo. In particolare i passi da seguire sono:

• si codifica ${\displaystyle \left|valore\right|}$ con le regole indicate sopra
• si calcola il Complemento a uno cioè si nega bit a bit
• si aggiunge infine al numero ottenuto ${\displaystyle +1_{2}}$

Ad esempio se valore = -100 si ha:

• ${\displaystyle \left|valore\right|=\left|-100\right|=100_{10}=01100100_{2}}$ (vedi es. INTEGER Positivi)
• complemento a 1: ${\displaystyle 01100100_{2}->10011011_{2}}$
• aggiungere ${\displaystyle +1_{2}}$. Si ottiene ${\displaystyle 10011011_{2}+1_{2}=10011100_{2}}$

Quindi ${\displaystyle valore=-100\to V=10011100_{2}=9C_{16}}$

Se invece valore = -250 si ha:

• ${\displaystyle \left|valore\right|=\left|-250\right|=250_{10}=0000000011111010_{2}}$ (vedi es. INTEGER Positivi)
• complemento a 1: ${\displaystyle 0000000011111010_{2}->1111111100000101_{2}}$
• aggiungere ${\displaystyle +1_{2}}$. Si ottine ${\displaystyle 1111111100000101_{2}+1_{2}=1111111100000110_{2}}$

Quindi ${\displaystyle valore=-250\to V=1111111100000110_{2}=FF06_{16}}$

In ASN.1 sono definite una grande varietà di stringhe, ma l'OCTECT STRING è quella fondamentale. In questo caso ogni carattere occupa 1 byte e viene utilizzata la codifica ASCII.

Ad esempio l'OCTECT STRING "ciao" viene codificato in 4 byte in ${\displaystyle 6369616F_{16}}$

Un OBJECT IDENTIFIER (abbreviato è OID) è un identificatore univoco di un campo della MIB.

Un OID è formato da n numeri divisi da n-1 punti. Un esempio di OID è il seguente: 1.2.250.1.16.9

I passi per codificare un OID sono i seguenti:

1. si pone nel primo byte il valore ${\displaystyle 40*primonumero+secondonumero}$
2. si codificano gli altri numeri in byte separati con le seguenti regole:
   1. se ${\displaystyle numero<=127}$ si usa semplicemente la rappresentazione binaria di numero
   2. se ${\displaystyle numero>127}$ si usa la rappresentazione binaria di numero con:
      1. uno 0 inframezzato ad ogni 7 bit
      2. un 1 come primo bit del primo byte

Ad esempio codifica di 1.2.250.1.16.9:

• ${\displaystyle primobyte=40*1+2=42_{10}=2A_{16}}$
• ${\displaystyle 250_{10}=FA_{16}=11111010_{2}}$ -> 1000 0001 | 0111 1010 -> 1000 0001 0111 1010 = ${\displaystyle 817A_{16}}$
• ${\displaystyle 1_{10}=01_{16}}$
• ${\displaystyle 16_{10}=10_{16}}$
• ${\displaystyle 9_{10}=09_{16}}$

Quindi 1.2.250.1.16.9 -> 2A 817A 01 10 09 = ${\displaystyle 2A817A011009_{16}}$

• Simple Network Management Protocol
• Lightweight Directory Access Protocol

• Wikimedia Commons contiene immagini o altri file su Basic Encoding Rules

• (EN) Olivier Dubuisson - ASN.1: Communication Between Heterogeneous Systems - Free PDF book
• (EN) Professor John Larmouth - ASN.1 Complete - Free PDF book