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]

TLV kódování
1..(tLen)(tLen+1)..(tLen+1+lLen)(1+tLen+lLen+1)..(1+tLen+lLen+1+vLen)
TypeLengthValue (délky Length)

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:

Oktet s identifikátorem typu
87654321
TřídaP/CČíslo Tagu

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

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

Třídabit 8bit 7
Universal (univerzální)00
Application (definované aplikací)01
Context-specific (kontextově závislé)10
Private (definované privátním standardem)11

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):

P/Cbit 6
Primitive0
Constructed1

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

Tagy třídy Universal
P/CČíslo (desítkově)Číslo (šestnáctkově)
EOC (End-of-Content koncová značka)P00
BOOLEAN (logická hodnota)P11
INTEGER (celé číslo)P22
BIT STRING (bitový řetězec)P/C33
OCTET STRING (řetězec bytů)P/C44
NULL (prázdná hodnota)P55
OBJECT IDENTIFIER (identifikátor objektu)P66
Object Descriptor (popisovač objektu)P/C77
EXTERNAL (externí)C88
REAL (číslo s pohyblivou řádovou čárkou)P99
ENUMERATED (výčet)P10A
EMBEDDED PDV (vložené PDV)C11B
UTF8String (řetězec v kódování UTF-8)P/C12C
RELATIVE-OID (relativní identifikátor objektu)P13D
reserved (rezervováno)-14E
reserved (rezervováno)-15F
SEQUENCE and SEQUENCE OF (posloupnost)C1610
SET and SET OF (množina)C1711
NumericString (číslo zapsané jako řetězec)P/C1812
PrintableString (tisknutelný řetězec)P/C1913
T61String (řetězec v kódování T.61)P/C2014
VideotexString (řetězec pro Videotex)P/C2115
IA5String (řetězec k kódování IA5)P/C2216
UTCTime (časový údaj v UTC)P/C2317
GeneralizedTime (časový údaj)P/C2418
GraphicString (grafický řetězec)P/C2519
VisibleString (viditelný řetězec)P/C261A
GeneralString (obecný řetězec)P/C271B
UniversalString (univerzální řetězec)P/C281C
CHARACTER STRING (znakový řetězec)P/C291D
BMPString (řetězec v kódu BMP)P/C301E
use long-form (pro rozšíření)-311F

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 0016 až 7F16, je to délka pole.
  • Hodnota 8016 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 = 8116 až FE16, pak je délka hodnoty obsažena v následujících 'n – 8016' oktetech (big endian).
  • Hodnota FF16 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:

HodnotaKódování
„nepravda“0116, 0116, 0016
„pravda“0116, 0116, FF16

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:

HodnotaKódování
00216, 0116, 0016
10216, 0116, 0116
-10216, 0116, FF16
1270216, 0116, 7F16
1280216, 0216, 0016, 8016
-10000216, 0216, FC16, 1816

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í:

hLengthPrvní oktet z Value
002160716
102160616
202160516
302160416
402160316
502160216
602160116
702160016
803160716
903160616
hLengthPrvní oktet z Value
1003160516
1103160416
1203160316
1303160216
1403160116
1503160016
1604160716
1704160616
1804160516
1904160416
hLengthPrvní oktet z Value
2004160316
2104160216
2204160116
2304160016
2405160716
2505160616
2605160516
2705160416
2805160316
2905160216

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 8016, 0216, 0716, 8016 ([0] za protocol-version se chápe jako typ třídy Context-specific s hodnotou 0, proto Type je 8016; 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 8016.

  • 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 0316, 0316, 0216, 5316, 4016. 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 0516, 0016; v BER se mohou objevit i delší formy jako 0516, 8116, 0016 nebo 0516, 8216, 0016, 0016, 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 o1, o2, … on, tak že o1, o2, … on-1 mají hodnotu větší nebo rovnu 128 a on má hodnotu menší než 128, což signalizuje konec kódu pro příslušné číslo; výsledná hodnota = (o1-128)×128n-1 + (o2-128)×128n-2 + … + on.

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.

  1. a b c ITU-T X.690, ISO 8825-1
  2. Olivier Dubuisson: "ASN.1 - Communication between Heterogeneous Systems", strana 396.
  3. a b Lin, Huai-An. “Estimation of the Optimal Performance of ASN.1/BER Transfer Syntax”. ACM Computer Communication Review. July 93, 45 - 58.
  4. a b ITU-T Rec. X.892, ISO/IEC 24824-2
  5. a b ITU-T X.694, ISO/IEC ISO/IEC 8825-5

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) 
  • KALISKI, JR., Burton. A Layman's Guide to a Subset of ASN.1, BER, and DER. [s.l.]: [s.n.] Dostupné online. (anglicky) 
  • LARMOUTH, John. ASN.1 Complete. [s.l.]: [s.n.] Dostupné v archivu pořízeném z originálu dne 2008-12-05. (anglicky) 
  • 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) 
  • 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) 

Související články

Externí odkazy