Basic Encoding Rules

Basic Encoding Rules (BER) je jeden z formátů kódování pro ASN.1 podle ITU specifikace X.690.

Basic Encoding Rules jsou původní pravidla standardu ASN.1 pro zakódování abstraktní informace do konkrétního datového proudu. Pravidla v jazyce standardu ASN.1 označovaná jako transfer syntax definují konkrétní posloupnosti oktetů, které slouží pro zakódování dané datové položky. Syntaxe definuje:

• reprezentaci jednoduchých datových typů
• strukturu informace o délce
• prostředky umožňující definovat komplexní datové typy skládáním z jednoduchých typů.

BER je spolu se svými dvěma podmnožinami (Canonical Encoding Rules a Distinguished Encoding Rules) definován ITU-T standardem X.690, který patří do sady dokumentů popisujících ASN.1.

Kódování

BER definuje formát pro kódování datových struktur podle ASN.1. BER popisuje typy jednotlivých položek struktur a dovoluje zjistit jejich hranice. Do míst, kde je to nutné, lze vložit označení konce dat (end-of-content marker). Každý datový prvek (data element) je zakódovaný jako trojice

• Type – identifikátor typu
• Length – informace o délce
• Value – vlastní hodnota

Tím se BER řadí k type-length-value (TLV) formátům. BER umožňuje na přijímací straně dekódovat ASN.1 informace z neúplného proudu dat bez potřeby znát velikost obsah nebo význam dat.^[1]

Kódování PDU sestává z hierarchie TLV struktur; složené struktury se vytváří pomocí typů SEQUENCE (posloupnost), SET (množina) a CHOICE (alternativa).

Typ

Pole Type určuje typ nebo význam hodnoty. První oktet má následující strukturu:

Pokud číslo tagu má hodnotu 31 (1F₁₆), je typ víceoktetový a končí oktetem s hodnotou menší než 128 (80₁₆).

Horní dva bity pole Type udávají jeho třídu (Class):

Typy třídy Universal (např. INTEGER) definuje přímo standard ASN.1; typy třídy Private mohou být definovány jinými standardy. Typy s třídou Application si může nadefinovat každá aplikace podle svých potřeb; typy s třídou Context-specific závisí na kontextu (mohou mít různý význam uvnitř různých typů sequence, set nebo choice).

Bit P/C slouží k rozlišení, zda je hodnota jednoduchá (primitive) nebo složená (constructed):

Spodních 6 bitů Číslo tagu určuje konkrétní tag, případně přesný typ hodnoty:

Další informace z http://luca.ntop.org/Teaching/Appunti/asn1.html:

Bit P/C (primitive/constructed) má hodnotu 0 pro jednoduché typy (primitive) a 1 pro složené (constructed). Některé typy (např. řetězce) mohou být kódovány jako jednoduché i složené typy. Pokud jsou kódovány jako jednoduché, pole s hodnotou obsahuje reprezentaci položky tagovaných dat, zatímco když kódování je constructed, hodnota obsahuje posloupnost TLV.

Pokud má pole Tag hodnotu 1F (hex), je číslo tagu uloženo v několika následujících oktetech; spodních 7 bitů každého oktetu je část hodnoty a vrchní bit udává, zda následují další oktety (1 – ano, 0 – toto je poslední oktet); hodnoty z jednotlivých oktetů jsou v pořadí od nejvýznamnějších k nejméně významným.

Data (především prvky posloupností, množina a alternativ) mohou být označena unikátní hodnotou Tagu (v ASN.1 uvedenou v hranatých závorkách []), aby bylo možné rozlišit jednotlivé prvky. Tyto tagy mohou být implicitní (zakódované jako TLV tag hodnoty místo použití základního typu jako TLV tagu) nebo explicitní (tag je použit jako složené TLV, které obaluje TLV základního typu). Pokud není styl tagu výslovně uveden a v ASN.1 definici modulu není definován jako implicitní, je tagovací styl explicitní. Takové tagy mají třídu context-specific, pokud není před tagem uvedeno jiné jméno třídy.

Kódování hodnoty typu alternativa je stejné jako kódování vybrané (použité) hodnoty – tj. primitive nebo constructed podle vybraného typu. Tag použitý v oktetu s identifikátorem je tag vybraného typu jak je definovaný v ASN.1 definici.

Délka

Délka hodnoty (v oktetech) je zakódována takto:

• Pokud první oktet pole Length má hodnotu 00₁₆ až 7F₁₆, je to délka pole.
• Hodnota 80₁₆ prvního oktetu je povolena pouze pro složené typy a znamená „neurčenou délku“; struktura pak musí být zakončena EOC TLV.
• Pokud má první oktet hodnotu n = 81₁₆ až FE₁₆, pak je délka hodnoty obsažena v následujících 'n – 80₁₆' oktetech (big endian).
• Hodnota FF₁₆ prvního oktetu je rezervovaná pro budoucí rozšíření.^[2]

Kódování vybraných typů

Typ BOOLEAN

Typ BOOLEAN (Type=1) slouží k reprezentaci logické hodnoty. Nulová hodnota má význam „nepravda“ (false), nenulová hodnota má význam „pravda“ (true). Při použití DER nebo CER musí mít hodnota délku 1 oktet a pro hodnotu „pravda“ (true) se používá oktet tvořený samými jedničkovými bity. Příklady kompletního TLV:

Typ INTEGER

Typ INTEGER (Type=2) je celé číslo se znaménkem. Při délce hodnoty 1 oktet lze zobrazit čísla z intervalu -128 až 127, při délce 2 oktety z intervalu -32768 až 32767, při délce n oktetů čísla z intervalu -2^(8×n)-1 až 2^(8×n)-1-1. To znamená, že čísla z intervalu 128 až 255 je nutné zobrazit hodnotou s délkou 2 oktety. Při použití DER nebo CER nesmí být 9 nejvyšších bitů čísla tvořeno samými jedničkami nebo samými nulami (pokud by tomu tak bylo, bylo by nutné vypustit první oktet hodnoty). Příklady kompletního TLV:

Typ BIT STRING

Typ BIT STRING (Type=3) je bitový řetězec. Jeho hodnota může být jednoduchá i složená. Pokud je jednoduchá, obsahuje první oktet hodnoty číslo 0 až 7 udávající počet nevyužitých bitů v posledním oktetu. Počet nevyužitých bitů nezáleží ani na konkrétní hodnotě bitového řetězce, ani na SIZE uvedené v ASN.1 definici, ale na nejvyšším čísle bitu použitém v ASN.1 definici. Pokud označíme tuto hodnotu h, pak pro délku a první byte hodnoty platí:

Další oktety jsou použity pro uložení jednotlivých bitů bitového řetězce: první bit řetězce je uložen v nejvyšším bitu druhého oktetu hodnoty, druhý bit řetězce v druhém nejvyšším bitu druhého oktetu hodnoty, atd. až osmý bit řetězce v nejnižším bitu druhého oktetu hodnoty; devátý bit řetězce v nejvyšším bitu třetího oktetu hodnoty atd.

Příklady:

• Pole protocol-version v TCAP je definováno v ITU-T doporučení Q.773 takto:

  AARQ-apdu ::= [APPLICATION 0] IMPLICIT SEQUENCE {
      protocol-version [0] IMPLICIT BIT STRING { version1 (0) }
      DEFAULT { version1 },
      ...
  }
  

  Hodnota protocol-version tvořená bitovým řetězcem 1 bude zakódován 80₁₆, 02₁₆, 07₁₆, 80₁₆ ([0] za protocol-version se chápe jako typ třídy Context-specific s hodnotou 0, proto Type je 80₁₆; v definici je uveden pouze jeden bit se jménem version1 s hodnotou 0, proto je h=0 a tedy podle tabulky výše je délka 2 a počet nevyužitých bitů 7; bitový řetězec tvořený jednou jedničkou pak dá hodnotu 80₁₆.

• Bitový řetězec 01010011010000 obsahuje 14 bitů. To znamená, že samotný řetězec bude zabírat dva oktety a počet nevyužitých bitů je 2 (i když by pro přenesení začátku řetězce tvořeného nenulovými bity stačilo 10 bitů, takže zdánlivě by mohl být počet nevyužitých bitů 6). V DER bude zakódován jako 03₁₆, 03₁₆, 02₁₆, 53₁₆, 40₁₆. V BER kódování mohou mít nevyužité bity libovolnou hodnotu (v DER musí být nulové). V BER může být také použita jiná než nejkratší možná reprezentace délky.

Složený bitový řetězec má hodnotu tvořenou posloupností jednoduchých bitových řetězců. DER složené řetězce nepovoluje.

Typ OCTET STRING

Typ OCTET STRING (Type=4) je řetězec oktetů. Jeho hodnota může být jednoduchá i složená. U jednoduché hodnoty je hodnota přímo tvořena jednotlivými oktety. Délka může být i nulová. Složený řetězec oktetů má hodnotu tvořenou posloupností jednoduchých řetězců oktetů (trojic Type-Length-Value).

Typ NULL

Typ NULL (Type=5) je prázdný typ. Obvykle se používá jako jednobitový příznak definovaný v ASN.1 jako OPTIONAL. Informace je nesena jeho přítomností nebo nepřítomností ve složeném typu. Jeho DER kódování je 05₁₆, 00₁₆; v BER se mohou objevit i delší formy jako 05₁₆, 81₁₆, 00₁₆ nebo 05₁₆, 82₁₆, 00₁₆, 00₁₆, atd.

Typ OBJECT IDENTIFIER

Pro identifikátor objektu, což je posloupnost čísel, která se zapisuje jako několik desítkových čísel oddělených tečkami (například 0.17.773.1.1.1), se používá typ OBJECT IDENTIFIER (Type=6). Protože první složka může nabývat hodnot 0 až 2 a druhá složka musí být menší než 40, jsou první dvě složky spojeny do jedné; identifikátor objektu a1.a2.a3.a4.a5 se zakóduje jako posloupnost čísel 40×a1+a2, a3, a4, a5 (číslo 40 je v desítkové soustavě). Pokud je libovolné číslo z posloupnosti menší než 128, je zakódováno jediným oktetem, obsahujícím příslušnou hodnotu. Pokud má číslo hodnotu větší nebo rovnu 128, bude zakódováno pomocí více oktetů s hodnotami o₁, o₂, … o_n, tak že o₁, o₂, … o_n-1 mají hodnotu větší nebo rovnu 128 a o_n má hodnotu menší než 128, což signalizuje konec kódu pro příslušné číslo; výsledná hodnota = (o₁-128)×128^n-1 + (o₂-128)×128^n-2 + … + o_n.

Typ PrintableString

PrintableString je univerzální Tag v ASN.1 notaci.

Podle RFC 3280 [1] je PrintableString přípustná znaková sada pro datový typ DirectoryName. PrintableString sestává z podmnožiny znakové sady ASCII a neobsahuje znaky zavináč (@ anglicky at sign) a ampersand (&). To způsobuje problémy v naivních implementacích, které se snaží uložit SMTP e-mailovou adresu do položky Distinguished Name v digitálním certifikátu podle standardu X.509.

Podle Layman's Guide to a Subset of ASN.1, BER, and DER [2] (Laický průvodce částí ASN.1, BER a DER), lze znakovou sadu typu PrintableString vyjádřit takto:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
a b c d e f g h i j k l m n o p q r s t u v w x y z
0 1 2 3 4 5 6 7 8 9
mezera ' ( ) + , - . / : = ?

Kódování CER

Kódování CER je omezenou variantou BER pro vytváření jednoznačné přenosové syntaxe pro datové struktur popsané ASN.1. Zatímco BER umožňuje volbu, jak mohou datové hodnoty být zakódovány, kódování CER a DER) vybírá pouze jedno z kódování povolených BER, a nepovoluje žádné varianty. Kódování CER je užitečné, když kódování musí být zachováno, např. v bezpečnostních dialozích.

Kódování DER

DER je omezenou variantou BER pro vytváření jednoznačné přenosové syntaxe pro datové struktury popsané ASN.1. Stejně jako CER, je kódování DER validním kódováním BER. DER je totéž jako BER s odstraněnou nejednoznačností nebo možností volby reprezentace odesilatelem.

DER je podmnožina BER, která poskytuje právě jeden způsob pro zakódování ASN.1 hodnot. DER je určeno pro situace, kdy je potřeba jednoznačné kódování, jako v kryptografii a zajišťuje, že datová struktura, která má být digitálně podepsána dává jednoznačně serializovanou reprezentaci. DER lze považovat ze kanonickou formu BER. Například logické hodnoty Boolean hodnoty pravda (true) v BER může být zakódována jako libovolná z 255 nenulových hodnot bytu, zatímco v DER existuje jen jeden způsob zakódování logické hodnoty "true".

Nejdůležitější omezení kódování DER jsou:

1. Zakódovaná délka musí používat určitou formu
   • Musí být použito kódování s nejkratší možnou délkou
2. Typy BITSTRING, OCTET STRING a omezené znakové řetězce musí používat primitivní kódování
3. Prvky množiny (SET) jsou zakódovány setříděné podle hodnoty tag

DER se široce používá pro digitální certifikáty jako je X.509.

Porovnání BER, CER a DER

Základní rozdíl mezi formátem BER kódováním CER nebo DER je flexibilita poskytovaná Basic Encoding Rules. Jak bylo vysvětleno výše, BER je základní sada kódovacích pravidel pro přenos datových struktur ASN.1 definovaných ITU X.690. Dává odesilateli jasná pravidla jak zakódovat datové struktury, které mají být přeneseny, ale stále ponechává určitou volnost v kódování. Jak je uvedeno ve standardu X.690, "BER umožňuje alternativní kódování podle volby odesilatele. Příjemce, který udává shodu s BER musí podporovat všechny alternativy".^[1]

Příjemce musí být schopen přijímat všechna povolená kódování, aby mohl deklarovat, že odpovídá BER standardu. CER a DER naopak omezují možné způsoby zadání délky pole na jedinou možnost. CER a DER jsou speciálními formami BER a slouží pro zjednoznačnění kódování BER.

CER a DER se liší sadou omezení, které vynucují od odesilatele. Základní rozdíl mezi CER a DER je, že DER používá určité údaje o délce, zatímco CER používá ve stejných případech neurčité údaje. To znamená, že DER vždy obsahuje informaci o délce na začátku, zatímco CER používá datový element EOC (end-of-contents, koncová značka) místo uvedení délky zakódovaných dat. Díky tomu CER vyžaduje méně metadat pro větší zakódované hodnoty, zatímco DER vyžaduje méně metadat pro menší zakódované hodnoty.

Pro výběr, jaká kódovací pravidla použít, poskytuje standard X.690 následující vodítka:

DER je vhodnější než CER, pokud se zakódované struktury vejdou do dostupné paměti a je potřeba rychle přeskakovat některé vnořené hodnoty. Naproti tomu kódování CER je vhodnější, pokud je potřeba zakódovat a odvysílat část datové struktury dříve, než je dostupná celá hodnota, nebo když je potřeba zakódovat rozsáhlé struktury, které se nevejdou do dostupné paměti. BER je vhodnější než CER nebo DER, pokud kódování obsahuje hodnoty SET nebo SET-OF a nejsou potřeba omezení daná CER a DER.

Kritika kódování BER

Kódování BER bývá často chápáno jako "neefektivní" v porovnání s alternativními kódovacími pravidly. Někteří autoři tvrdí, že tento pocit pramení především ze špatných implementací, a není principiálním nedostatkem kódovacích pravidel.^[3] Tyto implementace spoléhají na flexibilitu, kterou BER poskytuje pro použití kódovací logiky, kterou je snazší implementovat, ale vytváří větší zakódované datové proudy než je nezbytné. Ať je tato neefektivita realitou nebo jen pocitem, vedla k vytvoření několika alternativních kódovacích schémat, jako Packed Encoding Rules, které se snaží vylepšit výkonnost a velikost BER.

Byla vyvinuta další formátovací pravidla, která stále poskytují flexibilitu BER, ale používají alternativní kódovací schémata. Nejoblíbenější z nich jsou schémata vycházející z XML, jako XML Encoding Rules a ASN.1 SOAP.^[4] Existuje i standardní mapování pro konverzi XML schématu na ASN.1 schéma, které pak může být zakódováno pomocí BER.^[5]

Porovnání s alternativními formáty

Formát BER ponechává na rozdíl od formátů CER a DER určitou volnost ve způsobu reprezentace dat. Podle standardu X.690 „Vysílající strana může volit z několika kódování. Pokud přijímající strana deklaruje svoji schopnost zpracovávat BER, musí být schopná zpracovat všechny alternativy.“ Například při kódování složené hodnoty může vysílající strana zvolit jednu ze tří možných forem udání délky dat.^[1] Přijímající strana musí být schopná přijmout všechny tři alternativy, aby mohla deklarovat, že podporuje BER. Naproti tomu CER a DER dovolují pouze jednu možnost pro udání délky.

Ačkoli je obecně BER vnímáno jako „méně efektivní“ v porovnání s alternativními kódovacími pravidly, při kvalitní implementaci je stejně efektivní jako CER a DER.^[3] Tyto implementace využívají pružnosti, kterou umožňuje BER, k maximálnímu zjednodušení kodéru, který ale ne vždy vytváří optimální kódovanou reprezentaci. Ať je tato neefektivita realitou nebo jen pocitem, vedla k vytvoření několika alternativní kódovacích schémat, jako Packed Encoding Rules, která se snaží zlepšit výkonnost BER i velikost produkovaných dat.

Byla vyvinuta i další alternativní formátovací schémata, která jsou stejně flexibilní jako BER. Nejoblíbenější je jsou alternativy založené na XML jako XML Encoding Rules a ASN.1 SOAP.^[4] Navíc existuje standardní mapování pro konverzi XML Schématu na ASN.1 schéma, které může být zakódováno pomocí BER.^[5]

Použití

Přes některé problémy je BER oblíbený formát pro přenos dat, zvláště mezi systémy s různými nativními kódováními dat.

• Protokoly SNMP a LDAP používají ASN.1 a BER jako své povinné kódovací schéma.
• Standard EMV pro bankovní karty kredit používá BER pro kódování dat na kartě
• Standard PKCS #7 pro digitální podpis používá ASN.1 s BER pro kódování zašifrovaných zpráv, jejich digitálních podpisů a digitálních obálek.
• Standard X.509 pro certifikáty s veřejným klíčem používá ASN.1 s BER.
• Telekomunikační systémy používající TCAP, jako například ISDN, signalizace v SS7 sítích používající MAP a směrování bezplatných hovorů používá intenzivně ASN.1 s BER.
• GSM TAP (Transferred Account Procedures), NRTRDE (Near Real Time Roaming Data Exchange) soubory jsou kódovány pomocí BER. [3]

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Basic Encoding Rules na anglické Wikipedii.

Literatura

• HOUSLEY, R.; POLK, W.; FORD, W.; SOLO, D. Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile. [s.l.]: [s.n.] Dostupné online. (anglicky) Je zde použita šablona {{Citation}} označená jako k „pouze dočasnému použití“.
• KALISKI, JR., Burton. A Layman's Guide to a Subset of ASN.1, BER, and DER. [s.l.]: [s.n.] Dostupné online. (anglicky) Je zde použita šablona {{Citation}} označená jako k „pouze dočasnému použití“.
• LARMOUTH, John. ASN.1 Complete. [s.l.]: [s.n.] Dostupné v archivu pořízeném z originálu dne 2008-12-05. (anglicky) Je zde použita šablona {{Citation}} označená jako k „pouze dočasnému použití“.
• DUBUISSON, Olivier. ASN.1 - Communication Between Heterogeneous Systems. [s.l.]: [s.n.] Dostupné v archivu pořízeném z originálu dne 2008-12-05. (anglicky) Je zde použita šablona {{Citation}} označená jako k „pouze dočasnému použití“.
• ITU-T. Information technology – Abstract Syntax Notation One (ASN.1): Specification of basic notation (X.680 - 07/2002). [s.l.]: [s.n.] Dostupné online. (anglicky) Je zde použita šablona {{Citation}} označená jako k „pouze dočasnému použití“.

Související články

• ASN.1
• Canonical Encoding Rules
• Distinguished Encoding Rules
• Packed Encoding Rules
• SNMP
• Kerberos
• Serializace

Externí odkazy

• Obrázky, zvuky či videa k tématu Basic Encoding Rules na Wikimedia Commons

• ITU-T X.690, ISO/IEC 8825-1
• ITU-T X.892, ISO/IEC 24824-2
• ITU-T X.694, ISO/IEC ISO/IEC 8825-5
• PKCS #7
• simple BER tutorial
• jASN1 Java ASN.1 BER encoding/decoding library at beanit.com
• Peter Gutmann's 'X.509 Style Guide' [4]
• RSA's 'A Layman's Guide to a Subset of ASN.1, BER, and DER ' [5]^{[nedostupný zdroj]}