apontamentos de seguranca

7/31/2019 Apontamentos de Seguranca

1/62

Table of Contents

ACID ...................................................................................................................................................................3Principio de Kerckhoffs .......................................................................................................................................3Critrios de Shannon ...........................................................................................................................................3

Criptografia Clssica ...........................................................................................................................................4Criptografia simtrica ..........................................................................................................................................4Cifras de Bloco ....................................................................................................................................................5

DES ("Data Encryption Standard") ..........................................................................................................5Use and export of DES ..................................................................................................................6

DES modes ........................................................................................................................6DES strength ......................................................................................................................7

Improving the Security of DES .....................................................................................................8Double DES .......................................................................................................................8Triple DES .........................................................................................................................9

IDEA ......................................................................................................................................................10Key schedule ...............................................................................................................................11

AES ........................................................................................................................................................11Utilizao de cifras de bloco ..................................................................................................................11

Electronic codebook (ECB) ........................................................................................................11Cipher-block chaining (CBC) .....................................................................................................12Output feedback (OFB) ...............................................................................................................13Counter (CTR) ............................................................................................................................15

One-time pad ..........................................................................................................................................16Criptografia asimtrica ......................................................................................................................................16

Diffie-Hellman .......................................................................................................................................17RSA ........................................................................................................................................................18Gerao das chaves ................................................................................................................................18Cifrao ..................................................................................................................................................18Decifrao ..............................................................................................................................................19

Hash Segura .......................................................................................................................................................20MD-5 ......................................................................................................................................................21

Algoritmo ....................................................................................................................................21Vulnerabilidade ...........................................................................................................................22

SHA-1 .....................................................................................................................................................22Checksums Criptogrficos .................................................................................................................................24

HMAC ....................................................................................................................................................25Assinaturas digitais ............................................................................................................................................26

Propriedades a verificar ..........................................................................................................................27Assinatura arbitrada ................................................................................................................................27Assinatura directa ...................................................................................................................................28DSA/DSS ...............................................................................................................................................28

Autoridade certificadora ....................................................................................................................................28X.509 ......................................................................................................................................................29

Structure of a certificate ..............................................................................................................29

Sample X.509 certificates .......................................................................................................................30Self-signed certificate .............................................................................................................................30Centro de distribuio de chaves (KDC) ...........................................................................................................31Assinatura cega ..................................................................................................................................................31

Blind RSA signatures .............................................................................................................................32Dangers of blind signing ........................................................................................................................33Zero-knowledge ......................................................................................................................................34

Abstract example .........................................................................................................................34Definition ....................................................................................................................................34Practical example ........................................................................................................................35


2/62

Variants of zero-knowledge ........................................................................................................37Applications ................................................................................................................................37

Dinheiro digital ..................................................................................................................................................38How does Digital Cash work? ................................................................................................................38Key Properties of a Private Digital Cash System ...................................................................................38

Comunicao segura ..........................................................................................................................................40Canal seguro ...........................................................................................................................................40

Secure channels in the real world ...............................................................................................40Trusted computering base ..................................................................................................................................41

Definition and characterization ..............................................................................................................41Properties of the TCB .............................................................................................................................42

Predicated upon the security policy: TCB is in the eye of the consultant ...............................42A prerequisite to security ............................................................................................................42Software parts of the TCB need to protect themselves ...............................................................43Trusted vs. trustworthy ...............................................................................................................43TCB size ......................................................................................................................................44

Matriz de controlo de acesso ..................................................................................................................44Lista de controlo de acesso .....................................................................................................................44Lista s de capacidade ..............................................................................................................................44Controlo de acesso descriminatorio (DAC) ...........................................................................................45

Controlo de acesso mandatario ...............................................................................................................45Modelos de autenticao ....................................................................................................................................47

Kerberos .................................................................................................................................................47Protocolo .....................................................................................................................................47

User Client-based Logon .................................................................................................48Client Authentication .......................................................................................................48Client Service Authorization ...........................................................................................48Client Service Request .....................................................................................................49

Firewall ..............................................................................................................................................................49Comunicao segura...........................................................................................................................................51

SSL/TLS..................................................................................................................................................51Cipher suite..................................................................................................................................51Aplicao.....................................................................................................................................51

Segurana.....................................................................................................................................52How it works................................................................................................................................54TLS handshake in detail...............................................................................................................54

Simple TLS handshake.....................................................................................................55Client-authenticated TLS handshake................................................................................56Resumed TLS handshake.................................................................................................57

SSH..........................................................................................................................................................59IPSec...................................................................................................................................................................59PGP.....................................................................................................................................................................59

Compatibility...........................................................................................................................................60Digital signatures.....................................................................................................................................60Web of trust.............................................................................................................................................60Certificates...............................................................................................................................................61

Security quality........................................................................................................................................61


3/62

ACIDConfidencialidade - Medida em que um servio/informao esta protegido contra o acessoem leitura de intrusos.Integridade - medida em que um servio/informao esta protegido contra a

modificao/deteriorao por intrusos.Autenticidade - medida em que um servio/informao genuno, i.e., esta protegidocontra a personificao por intrusos.Disponibilidade - medida em que um servio/informao esta protegido contra a recusa deprovao/acesso provocada por intrusos.

Principio de KerckhoffsPara avaliar a segurana de uma tcnica criptogrfica devemos assumir que esta doconhecimento de eventuais inimigos.

Critrios de Shannon1. Quantidade de segredo

Sistema perfeito: Inimigo no aprende nada depois de interceptar a qualquerquantidade de dados cifrados.

2. Tamanho da chave

desejvel possuir uma chave menor possvel (transmisso no interceptavel,memorizao).

3. Complexidade das operaes de cifrao e decifrao

Deve ser mnima.

4. Propagao de erros

Um erro de transmisso pode causar muitos erros no texto depois de decifrar.

5. Expanso de mensagens

indesejvel aumentar o tamanho de texto depois de cifrao.


4/62

Criptografia ClssicaA criptografia pr-computacional era formada por um conjunto de mtodos de substituioe transposio dos caracteres de uma mensagem que pudessem ser executadosmanualmente (ou at mesmo mentalmente) pelo emissor e pelo destinatrio da mensagem.

O surgimento de mquinas especializadas e, posteriormente, dos computadores ocasionouuma significativa evoluo das tcnicas criptogrficas.

Criptografia simtrica

A encriptao consiste na aplicao de um algoritmo aos dados por forma a que eles setornem ilegveis, para recuperar os dados originais ser necessrio conhecer o algoritmo dedesencriptao.As aplicaes bsicas da criptografia so a confidencialidade (garantir que apenas quemautorizado pode ler os dados) e a autenticao/integridade (garantir que os dados tm aorigem correcta e que no foram alterados entre origem e destino).

Na prtica, juntamente com os algoritmos utilizam-se chaves, mesmo que os algoritmossejam conhecidos necessria a chave correta.

A criptografia simtrica, tambm conhecida por criptografia tradicional utiliza uma nicachave que serve tanto para cifrar como para decifrar. A criptografia de chave pblica (maisrecente) utiliza uma chave para cifrar e outra chave para decifrar.

No existem mecanismos 100% eficazes, numa abordagem puramente terica imediatoque qualquer chave pode ser quebrada pela fora bruta (supondo que dispe de umexemplar de uma mesma mensagem original e cifrada, e o algoritmo conhecido, bastatentar com todas as chaves possveis at acertar).

O tempo necessrio para quebrar uma chave pela "fora bruta" depende do nmero de


5/62

chaves possveis (nmero de bits da chave) e do tempo de execuo do algoritmo. O grandeproblema desta abordagem que a capacidade de processamento dos equipamentos temduplicado de 18 em 18 meses, logo de 18 em 18 meses necessrio aumentar um bit schaves.

Cifras de Bloco

DES ("Data Encryption Standard")

One of the most widely used encryption systems today is the Data Encryption Standard(DES), developed in the 1970s and patented by researchers at IBM. The DES was anoutgrowth of another IBM cipher known as Lucifer. IBM made the DES available forpublic use, and the federal government issued Federal Information Processing StandardPublication (FIPS PUB) Number 46 in 1977 describing the system. Since that time, theDES has been periodically reviewed and reaffirmed (most recently in December 30, 1993),until 1998 as FIPS PUB 46-2. It has also been adopted as an American National Standard(X3.92-1981/R1987).

The DES performs a series of bit permutation, substitution, and recombination operationson blocks containing 64 bits of data and 56 bits of key (eight 7-bit characters). The 64 bits

of input are permuted initially, and are then input to a function using static tables ofpermutations and substitutions (called S-boxes). The bits are permuted in combination with48 bits of the key in each round. This process is iterated 16 times (rounds), each time with adifferent set of tables and different bits from the key. The algorithm then performs a finalpermutation, and 64 bits of output are provided. The algorithm is structured in such a waythat changing any bit in the input has a major effect on almost all of the output bits. Indeed,the output of the DES function appears so unrelated to its input that the function issometimes used as a random number generator.


6/62

Although there is no standard UNIX program that performs encryption using the DES,some vendors' versions of UNIX include a program called des which performs DESencryption. (This command may not be present in international versions of the operatingsystem, as described in the next section.)

Use and export of DESThe DES was mandated as the encryption method to be used by all federal agencies inprotecting sensitive but not classified information.[15] The DES is heavily used in manyfinancial and communication exchanges. Many vendors make DES chips that can encode ordecode information fast enough to be used in data-encrypting modems or networkinterfaces. Note that the DES is not (and has never been) certified as an encryption methodthat can be used with U.S. Department of Defense classified material.

Export control rules restrict the export of hardware or software implementations of theDES, even though the algorithm has been widely published and implemented many timesoutside the United States. If you have the international version of UNIX, you may find that

your system lacks a des command. If you find yourself in this position, don't worry; goodimplementations of the DES can be obtained via anonymous FTP from almost any archiveservice, including the Usenet comp.sources archives.

For more information about export of cryptography, see "Encryption and U.S. Law," laterin this chapter.

DES modes

FIPS PUB 81 explains how the DES algorithm can be used in four modes:

Electronic Code Book (ECB)Cipher Block Chaining (CBC)Cipher Feedback (CFB)Output Feedback (OFB)

Each mode has particular advantages in some circumstances, such as when transmitting textover a noisy channel, or when it is necessary to decrypt only a portion of a file. Thefollowing provides a brief discussion of these four methods; consult FIPS PUB 81 or agood textbook on cryptography for details.

ECB Mode. In electronic code book (ECB) mode, each block of the input is encrypted

using the same key, and the output is written as a block. This method performs simpleencryption of a message, a block at a time. This method may not indicate when portions ofa message have been inserted or removed. It works well with noisy transmission channels -alteration of a few bits will corrupt only a single 64-bit block.

CBC Mode. In cipher block chaining (CBC) mode, the plaintext is first XOR'ed with theencrypted value of the previous block. Some known value (usually referred to as theinitialization vector, or IV) is used for the first block. The result is then encrypted using the


7/62

key. Unlike ECB mode, long runs of repeated characters in the plaintext will be masked inthe output. CBC mode is the default mode for Sun Microsystems' des program.

CFB Mode. In cipher feedback (CFB) mode, the output is fed back into the mechanism.After each block is encrypted, part of it is shifted into a shift register. The contents of this

shift register are encrypted with the user's key value using (effectively) ECB mode, and thisoutput is XOR'd with the data stream to produce the encrypted result. This method is selfsynchronizing, and enables the user to decrypt only a portion of a large database by startinga fixed distance before the start of the desired data.

OFB Mode. In output feedback (OFB) mode, the output is also fed back into themechanism. A register is initialized with some known value (again, the IV). This register isthen encrypted with (effectively) ECB mode using the user's key. The result of this is usedas the key to encrypt the data block (using an XOR operation), and it is also stored backinto the register for use on the next block. The algorithm effectively generates a long streamof key bits that can be used to encrypt/decrypt communication streams, with good tolerancefor small bit errors in the transmission. This mode is almost never used in UNIX-basedsystems.

All of these modes require that byte and block boundaries remain synchronized between thesender and recipient. If information is inserted or removed from the encrypted data stream,it is likely that all of the following data from the point of modification can be renderedunintelligible.

DES strength

Ever since DES was first proposed as a national standard, some people have beensuspicious of the algorithm. DES was based on a proprietary encryption algorithm

developed by IBM called Lucifer, which IBM had submitted to the National Bureau ofStandards (NBS)[16] for consideration as a national cryptographic standard. But whereasLucifer had a key that was 112 bits long, the DES key was shortened to 56 bits at therequest of the National Security Agency. The NSA also requested that certain changes bemade in the algorithm's S-boxes. Many people suspected that NSA had intentionallyweakened the Lucifer algorithm, so the final standard adopted by NBS would not pose athreat to the NSA's ongoing intelligence collection activities. But nobody had any proof.

Today the DES is more than 20 years old, and the algorithm is definitely showing its age.Recently Michael Weiner, a researcher at Bell Northern Research, published a paperdetailing how to build a machine capable of decrypting messages encrypted with the DES

by conducting an exhaustive key search. Such a machine could be built for a few milliondollars, and could break any DES-encrypted message in about a day. We can reasonablyassume that such machines have been built by both governments and private industry.

In June 1994, IBM published a paper describing the design criteria of the DES. The paperclaims that the choices of the DES key size, S-boxes, and number of rounds were a directresult of the conflicting goals of making the DES simple enough to fit onto a single chipwith 1972 chip-making technology, and the desire to make it resistant to differential


8/62

cryptanalysis.

These two papers, coupled with many previously published analyses, appear to have finallysettled a long-running controversy as to whether or not NSA had intentionally built inweaknesses to the DES. The NSA didn't build a back door into DES that would have

allowed it to forcibly decrypt any DES-encrypted transmission: it didn't need to. Messagesencrypted with DES can be forcibly decrypted simply by trying every possible key, giventhe appropriate hardware.

Improving the Security of DES

You can improve the security of DES by performing multiple encryptions, known assuperencryption. The two most common ways of doing this are with double encryption(Double DES) and with triple encryption (Triple DES).

While double DES appears to add significant security, research has found some points ofattack, and therefore experts recommend Triple DES for applications where single DES is

not adequate.

Double DES

In Double DES, each 64-bit block of data is encrypted twice with the DES algorithm, firstwith one key, then with another, as follows:

Encrypt with (key 1).Encrypt with (key 2).

Plaintext (key1) (key2) ciphertext

Double DES is not significantly more secure than single DES. In 1981, Ralph Merkle andMartin Hellman published an article[17] in which they outlined a so-called "meet-in-the-middle attack."

[17] R. C. Merkle and M. Hellman, "On the Security of Multiple Encryption,"Communications of the ACM, Volume 24, Number 7, July 1981, pp. 465-467.

The meet-in-the-middle attack is a known plaintext attackwhich requires that an attackerhave both a known piece of plaintext and a block of that same text that has been encrypted.

(These pieces are surprisingly easily to get.) The attack requires storing 256 intermediate

results when trying to crack a message that has been encrypted with DES (a total of 259bytes), but it reduces the number of different keys you need to check from 2112 to 257."This is still considerably more memory storage than one could comfortably comprehend,but it's enough to convince the most paranoid of cryptographers that double encryption isnot worth anything," writes Bruce Schneier in his landmark volume,AppliedCryptography.


9/62

In other words, because a message encrypted with DES can be forcibly decrypted by anattacker performing an exhaustive key search today, an attacker might also be able toforcibly decrypt a message encrypted with Double DES using a meet-in-the-middle attackat some point in the future.

Triple DES

The dangers of the Merkle-Hellman meet-in-the-middle attack can be circumvented byperforming three block encryption operations. This method is called Triple DES.

In practice, the most common way to perform Triple DES is:

Encrypt with (key1).Decrypt with (key2).Encrypt with (key3).

The advantage of this technique is that it can be backward compatible with single DES,

simply by setting all three keys to be the same value.

To decrypt, reverse the steps:

Decrypt with (key3).Encrypt with (key2).Decrypt with (key1).

For many applications, you can use the same key for both key1 and key3 without creating asignificant vulnerability.

Triple DES appears to be roughly as secure as single DES would be if it had a 112-bit key.How secure is this really? Suppose you had an integrated circuit which could perform onemillion Triple DES encryptions per second, and you built a massive computer containingone million of these chips to forcibly try all Triple DES keys. This computer, capable of

testing 1012 encryptions per second, would require:

2112 = 5.19 x 1033 encryption operations

5.19 x 1033 encryption operations / 1012 operations/sec = 5.19 x 1021 sec

= 1.65 x 1014 years.

This is more than 16,453 times older than the currently estimated age of the universe

(approximately 1010 years).

Apparently, barring new discoveries uncovering fundamental flaws or weaknesses with theDES algorithm, or new breakthroughs in the field of cryptanalysis, Triple DES is the mostsecure private key encryption algorithm that humanity will ever need (although niche


10/62

opportunities may exist for faster algorithms).

IDEA

IDEA operates on 64-bit blocks using a 128-bit key, and consists of a series of eightidentical transformations (a round, see the illustration) and an output transformation (thehalf-round). The processes for encryption and decryption are similar. IDEA derives muchof its security by interleaving operations from different groups modular addition andmultiplication, and bitwise eXclusive OR (XOR) which are algebraically "incompatible"in some sense. In more detail, these operators, which all deal with 16-bit quantities, are:

Bitwise eXclusive OR (denoted with a blue circled plus ). Addition modulo 216 (denoted with a green boxed plus ).

Multiplication modulo 216+1, where the all-zero word (0x0000) is interpreted as

216 (denoted by a red circled dot ).

After the eight rounds comes a final "half round", the output transformation illustratedbelow:


11/62

Key schedule

Each round uses six 16-bit sub-keys, while the half-round uses four, a total of 52 for 8.5rounds. The first eight sub-keys are extracted directly from the key, with K1 from the firstround being the lower sixteen bits; further groups of eight keys are created by rotating themain key left 25 bits between each group of eight. This means that it is rotated less than

once per round, on average, for a total of six rotations.

AES

The Data Encryption Standard was found too weak because of its small key size and thetechnological advancements in processor power.

It takes an input block of a certain size, usually 128, and produces a corresponding outputblock of the same size. The transformation requires a second input, which is the secret key.It is important to know that the secret key can be of any size (depending on the cipher used)and that AES uses three different key sizes: 128, 192 and 256 bits.

Utilizao de cifras de bloco

Electronic codebook (ECB)

The simplest of the encryption modes is the electronic codebook (ECB) mode. The messageis divided into blocks and each block is encrypted separately.


12/62

The disadvantage of this method is that identical plaintext blocks are encrypted intoidentical ciphertext blocks; thus, it does not hide data patterns well. In some senses, itdoesn't provide serious message confidentiality, and it is not recommended for use incryptographic protocols at all.

Cipher-block chaining (CBC)

Each block of plaintext is XORed with the previous ciphertext block before beingencrypted. This way, each ciphertext block is dependent on all plaintext blocks processedup to that point. Also, to make each message unique, an initialization vector must be usedin the first block.


13/62

If the first block has index 1, the mathematical formula for CBC encryption is

while the mathematical formula for CBC decryption is

CBC has been the most commonly used mode of operation. Its main drawbacks are thatencryption is sequential (i.e., it cannot be parallelized), and that the message must bepadded to a multiple of the cipher block size. One way to handle this last issue is throughthe method known as ciphertext stealing.

Note that a one-bit change in a plaintext affects all following ciphertext blocks. A plaintextcan be recovered from just two adjacent blocks of ciphertext. As a consequence, decryptioncan be parallelized, and a one-bit change to the ciphertext causes complete corruption ofthe corresponding block of plaintext, and inverts the corresponding bit in the followingblock of plaintext.

Output feedback (OFB)

The output feedback(OFB) mode makes a block cipher into a synchronous stream cipher.It generates keystream blocks, which are then XORed with the plaintext blocks to get theciphertext. Just as with other stream ciphers, flipping a bit in the ciphertext produces aflipped bit in the plaintext at the same location. This property allows many error correctingcodes to function normally even when applied before encryption.

Because of the symmetry of the XOR operation, encryption and decryption are exactly thesame:


14/62

Each output feedback block cipher operation depends on all previous ones, and so cannotbe performed in parallel. However, because the plaintext or ciphertext is only used for thefinal XOR, the block cipher operations may be performed in advance, allowing the finalstep to be performed in parallel once the plaintext or ciphertext is available.

It is possible to obtain an OFB mode keystream by using CBC mode with a constant stringof zeroes as input. This can be useful, because it allows the usage of fast hardwareimplementations of CBC mode for OFB mode encryption.

Using OFB mode with limited feedback like CFB mode reduces the average cycle lengthby a factor of 232 or more. A mathematical model proposed by Davies and Parkin andsubstantiated by experimental results showed that only with full feedback an average cyclelength near to the obtainable maximum can be achieved. For this reason, support for limitedfeedback was removed from the specification of OFB.


15/62

Counter (CTR)

Like OFB, counter mode turns a block cipher into a stream cipher. It generates the nextkeystream block by encrypting successive values of a "counter". The counter can be anyfunction which produces a sequence which is guaranteed not to repeat for a long time,although an actual counter is the simplest and most popular. The usage of a simple

deterministic input function used to be controversial; critics argued that "deliberatelyexposing a cryptosystem to a known systematic input represents an unnecessary risk. " Bynow, CTR mode is widely accepted, and problems resulting from the input function arerecognized as a weakness of the underlying block cipher instead of the CTRmode.Nevertheless, there are specialized attacks like a Hardware Fault Attack that is basedon the usage of a simple counter function as input.

CTR mode has similar characteristics to OFB, but also allows a random access propertyduring decryption. CTR mode is well suited to operation on a multi-processor machinewhere blocks can be encrypted in parallel.

Note that the nonce in this graph is the same thing as the initialization vector (IV) in theother graphs. The IV/nonce and the counter can be concatenated, added, or XORed togetherto produce the actual unique counter block for encryption.


16/62

One-time pad

Em criptografia, one-time pad (OTP), ou cifra de chave nica, um algoritmo decriptografia onde oplaintext combinado com uma chave aleatria ou uma pad que sejato grande quanto oplaintexte usado somente uma vez. Uma adio modular (porexemplo XOR) usada para combinar oplaintextcom a pad.

Se a chave for verdadeiramente aleatria, nunca reutilizada, e mantida em segredo, a one-time pad pode ser inquebrvel. Tambm provou-se que toda a cifra terica inquebrveldeve usar chaves com as mesmas exigncias que chaves de OTP.

A chave consiste normalmente em um fluxo aleatrio de nmeros, cada qual indica onmero dos lugares no alfabeto (ou nmero de fluxos, se a mensagem do plaintextestiverno formulrio numrico) que a letra ou o nmero correspondente na mensagem doplaintextdevem ser deslocados. Para mensagens no alfabeto Latin, por exemplo, a chave consistirem uma cadeia aleatria dos nmeros de 0 a 25; para mensagens binrias a chave consistirem uma cadeia aleatria de 0s e de 1s; e assim por diante.

A parte pad do nome vem das primeiras implementaes onde as chaves eramdistribudas em um bloco de papel. Assim, a folha superior poderia facilmente ser removidae destruda depois de usada. Para facilitar sua ocultao, o bloco era s vezes muitopequeno.

Criptografia asimtricaA criptografia assimtrica um mtodo de criptografia que utiliza um par de chaves: umachave pblica e uma chave privada. A chave pblica distribuda livremente para todosos correspondentes via e-mail ou outras formas, enquanto a chave privada deve serconhecida apenas pelo seu dono.

Num algoritmo de criptografia assimtrica, uma mensagem cifrada com a chave pblicapode somente ser decifrada pela sua chave privada correspondente.

Os algoritmos de chave pblica podem ser utilizados para autenticidade econfidencialidade. Para confidencialidade, a chave pblica usada para cifrar mensagens,com isso apenas o dono da chave privada pode decifr-la. Para autenticidade, a chaveprivada usada para cifrar mensagens, com isso garante-se que apenas o dono da chaveprivada poderia ter cifrado a mensagem que foi decifrada com a 'chave pblica'.


17/62

Diffie-Hellman

1. usada para intercmbio de chaves entre utilizadores;

2. baseado na operao de logaritmos discretos;

3. Logaritmo discreto baseado na raiz primitiva;

4. Requer autoridade de certificao (chave pblica confivel).

Passos

1. Dados n primo e a uma raiz primitiva modulo n, ambos conhecidos pelos entes daconexo, nesse caso ser Alice e Bob;

2. Bob e Alice geram nmeros aleatrios Xa eXb, respectivamente, sendo queXa eXb somenores que n, esses nmeros gerados so as chaves privadas se comparado com ummtodo assimtrico;

3. Bob e Alice calculam as chaves pblicas Ya aXa(mod n), Yb aXb(mod n)

respectivamente;

4. Alice e Bob trocam as chaves (nmeros) publicas;

5. Bob calculaK YbXa(mod n)

KaXbXa(mod n)


18/62

Alice calculaK YaXb(mod n)

K aXaXb(mod n)

6. E assim eles possuem a mesma chave secreta K, vale ainda salientar que isso aconteceparaKsendo o menor numero inteiro positivo possvel, ou seja, 0


19/62

chave pblica do destinatrio e basta fazer uma potenciao modular:

A mensagem ento pode ser transmitida em canal inseguro para o receptor.

DecifraoPara recuperar a mensagem da mensagem cifrada usando a respectiva chave privada doreceptor e , basta fazer outra potenciao modular:


20/62

Hash SeguraUma funo "hash" tipica recebe como "input" uma mensagem de comprimento varivel eproduz um bloco de comprimento fixo que representa o contedo da mensagem. A funodeve ser tal que a minima alterao da mensagem produz uma alterao no bloco de saida.

Por outro lado a probabilidade de duas mensagens diferentes produzirem o mesmo blocodeve ser praticamente nula.

Os algoritmos "hash" mais conhecidos so:

"Message-Digest" (MD2; MD4 e MD5)(RFC 1320) - aceita mensagens de qualquertamanho e produz um bloco de 128 bits ("digest"), a mensagem inicialmentedividida em blocos de 512 bits que so processados.

SHA ("Secure Hash Algorithm") - aceita mensagens de comprimento inferior a 264

e produz um "digest" de 160 bits. Baseado no MD4, o facto de gerar mais 32 bits doque o MD4 torna-o partida mais seguro.

Um funo "hash" no proporciona autenticao, qualquer um pode criar uma mensagem egerar o respectivo "message digest" ou "hash code", para se conseguir autenticao necessrio usar conjuntamente algum mecanismo de cifragem, convencional ou no:

O conjunto mensagem/hash-code so cifrados. Neste caso existe confidencialidade. Apenas o "hash-code" cifrado. Se usada cifragem de chave secreta, torna-se

equivalente a um "checksum" criptogrfico. Se usada cifragem de chave pblicatemos ainda uma assinatura digital(*).

Uma outra opo possvel usar um valor secreto que concatenado mensagempara efeitos de clculo do "hash-code", mas no enviado.

(*) este tipo de assinatura pode ser atacado do seguinte modo ("birthday attack"):

A entidade X pretende realizar a fraude, ento produz um conjunto de variaes damensagem licita. Produz tambm um conjunto de variaes da mensagemfraudulenta.

De entre os dois conjuntos procura um par que produza o mesmo "hash-code", enviaento o exemplar licito a entidade A para esta "assinar".

A entidade A acrescenta a assinatura digital, ou seja calcula o "hash-code" e cifra-ocom a sua chave secreta.

A entidade X pode agora usar esta assinatura para a mensagem ilicita, como os"hash-code" so os mesmos, ento as assinaturas so iguais.

O grau de dificuldade com que este tipo de fraude realizado depende do nmero de "bits"

do "hash-code", para m bits ser necessrio comear por gerar dois conjuntos de 2m/2

mensagens, nesta situao a probabilidade de se conseguir um par adequado (mesmo hash-code) de 0,5 (50%).


21/62

MD-5

O MD5 (Message-Digest algorithm 5) um algoritmo de hash de 128 bits unidirecionaldesenvolvido pela RSA Data Security, Inc., descrito na RFC 1321, usado por softwarescom protocolo ponto-a-ponto (P2P), verificao de integridade e logins. Foi desenvolvidopara suceder ao MD4 que tinha alguns problemas de segurana.

Por ser um algoritmo unidirecional, um hash MD5 no pode ser transformado novamentena password (ou texto) que lhe deu origem. O mtodo de verificao , ento, feito pela

comparao das duas hash (uma da base de dados, e a outra da tentativa de login). O MD5tambm usado para verificar a integridade de um ficheiro atravs, por exemplo, doprograma md5sum, que cria a hash de um ficheiro. Isto pode-se tornar muito til paradownloads de ficheiros grandes, para programas P2P que constroem o ficheiro atravs depedaos e esto sujeitos corrupo de ficheiros.

O MD5 de domnio pblico para uso em geral. A partir de uma mensagem de umtamanho qualquer, ele gera um valor hash de 128 bits; com este algoritmo, computacionalmente impraticvel descobrir duas mensagens que gerem o mesmo valor,bem como reproduzir uma mensagem a partir do seu digest. O algoritmo MD5 utilizadocomo mecanismo de integridade em vrios protocolos de padro Internet (RFC1352,

RFC1446, etc.), bem como pelo CERT e CIAC.

Algoritmo

MD5 processes a variable-length message into a fixed-length output of 128 bits. The inputmessage is broken up into chunks of 512-bit blocks (sixteen 32-bit little endian integers);the message is padded so that its length is divisible by 512. The padding works as follows:


22/62

first a single bit, 1, is appended to the end of the message. This is followed by as manyzeros as are required to bring the length of the message up to 64 bits fewer than a multipleof 512. The remaining bits are filled up with a 64-bit integer representing the length of theoriginal message, in bits.

The main MD5 algorithm operates on a 128-bit state, divided into four 32-bit words,denotedA,B, CandD. These are initialized to certain fixed constants. The main algorithmthen operates on each 512-bit message block in turn, each block modifying the state. Theprocessing of a message block consists of four similar stages, termed rounds; each round iscomposed of 16 similar operations based on a non-linear function F, modular addition, andleft rotation. Figure illustrates one operation within a round. There are four possiblefunctionsF; a different one is used in each round:

denote the XOR, AND, OR and NOT operations respectively.

Vulnerabilidade

Como o MD5 faz apenas uma passagem sobre os dados, se dois prefixos com o mesmohash forem construdos, um sufixo comum pode ser adicionado a ambos para tornar umacoliso mais provvel. Deste modo possvel que duas strings diferentes produzam omesmo hash. O que no garante que a partir de uma senha criptografada especfica consiga-se a senha original, mas permite uma possibilidade de decifrar algumas senhas a partir de

um conjunto grande de senhas criptografadas.SHA-1

The Secure Hash Algorithm is one of a number of cryptographic hash functions publishedby the National Institute of Standards and Technology as a U.S. Federal InformationProcessing Standard. There are currently three generations of Secure Hash Algorithm:SHA-1 is the original 160-bit hash function. Resembling the earlier MD5 algorithm, thiswas designed by the National Security Agency (NSA) to be part of the Digital SignatureAlgorithm. Originally just called "SHA", it was withdrawn shortly after publication due toan undisclosed "significant flaw" and replaced by the slightly revised version SHA-1. Theoriginal withdrawn algorithm is now known by the retronym SHA-0.

SHA-2 is a family of two similar hash functions, with different block sizes, known as SHA-256 and SHA-512. They differ in the word size; SHA-256 uses 32-bit words where SHA-512 uses 64-bit words. There are also truncated versions of each standardized, known asSHA-224 and SHA-384. These were also designed by the NSA.

SHA-3 is a future hash function standard still in development. This is being chosen in apublic review process from non-government designers. An ongoing NIST hash function


23/62

competition is scheduled to end with the selection of a winning function, which will begiven the name SHA-3, in 2012.

The corresponding standards have been FIPS PUB 180 (original SHA), FIPS PUB 180-1(SHA-1), FIPS PUB 180-2 (SHA-1, SHA-256, SHA-384, and SHA-512), FIPS PUB 180-3

(SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512).

SHA-1 produces a 160-bit digest from a message with a maximum length of (264 1) bits.

SHA-1 is based on principles similar to those used by Ronald L. Rivest of MIT in thedesign of the MD4 and MD5 message digest algorithms, but has a more conservativedesign.

Algorithm and

variant

Output

size

(bits)

Internal

state size

(bits)

Block

size

(bits)

Max

message

size (bits)

Word

size

(bits)

Rounds OperationsCollisions

found

SHA-0 160 160 512 264 1 32 80+,and,or,xor,rot

Yes

SHA-1None

(263 attack)SHA-

2SHA-

256/224256/224 256 512 264 1 32 64

+,and,or,xor,shr,rot

None

SHA-

512/384 512/384 512 1024 2128

1 64 80

+,and,or,

xor,shr,rot None


24/62

Checksums CriptogrficosEsta tcnica envolve a utilizao de uma chave secreta, em conjunto com um algoritmo soaplicados mensagem e produzem um bloco de dados de dimenso fixa conhecido por"Checksum" Criptogrfico ou "Message Authentication Code" (MAC).

MAC = checksum(MENSAGEM,CHAVE SECRETA)

O MAC enviado em conjunto com a mensagem da entidade A para a entidade B, aentidade B gera tambm um MAC e verifica se coincide com o que chegou juntamente coma mensagem. Como apenas A e B conhecem a chave secreta, B sabe que a mensagem veiode A e no foi adulterada.

Como sempre algum pode recorrer fora bruta para tentar obter a chave secreta.Supondo que no se implementa confidencialidade, ento existe acesso pblico mensagem M e ao respectivo MAC, basta executar

MAC1 = checksum(MENSAGEM,CHAVE)

para todas as chaves possveis, tentando obter MAC = MAC1. Sendo k o nmero de bits daCHAVE, ento existe um total de 2k chaves possveis, este ser tambm o nmero deMAC's obtidos, contudo sendo n o nmero de bits do MAC, se n < k ento apenas seroproduzidos 2n < 2k MAC's diferentes.

Nestas condies ao empregar a fora bruta vo ser obtidas 2(k-n) chaves possveis. Sernecessrio recorrer a outro exemplar (M,MAC) e aplicar a mesma tcnica, agora apenassero testadas as 2(k-n) chaves obtidas no passo anterior, sero ento obtidas 2(k-2xn)chaves possiveis. Em mdia sero necessrios k/n passos destes at obter uma chave nica.Uma implementao comum de "Checksum" Criptogrfico o FIPS PUB 113 ou ANSIX9.17. O X9.17 basia-se no DES em modo CBC, com um vector inicial zero. Este

algoritmo tambm conhecido por DAA ("Data Authentication Algotithm"), usa umachave DES de 56 bits e produz um resultado de 64 bits, neste algoritmo o MAC tambmdesignado de DAC ("Data Authentication Code").

Para DAC pode utilizar-se menos do que os 64 bits produzidos pelo DAA. Neste casoutilizam-se pelo mesnos os 16 bits da esquerda.


25/62

HMAC

In cryptography, HMAC (Hash-based Message Authentication Code), is a specificconstruction for calculating a message authentication code (MAC) involving acryptographic hash function in combination with a secret key. As with any MAC, it may beused to simultaneously verify both the data integrity and the authenticity of a message. Anyiterative cryptographic hash function, such as MD5 or SHA-1, may be used in thecalculation of an HMAC; the resulting MAC algorithm is termed HMAC-MD5 or HMAC-

SHA1 accordingly. The cryptographic strength of the HMAC depends upon thecryptographic strength of the underlying hash function, the size of its hash output length inbits and on the size and quality of the cryptographic key.

An iterative hash function breaks up a message into blocks of a fixed size and iterates overthem with a compression function. For example, MD5 and SHA-1 operate on 512-bitblocks. The size of the output of HMAC is the same as that of the underlying hash function(128 or 160 bits in the case of MD5 or SHA-1, respectively), although it can be truncated ifdesired.

Let:

H() be a cryptographic hash function Kbe a secret key padded to the right with extra zeros to the block size of the hash

function m be the message to be authenticated

denote concatenation

denote exclusive or (XOR) opad be the outer padding (0x5c5c5c5c5c, one-block-long hexadecimal constant)


26/62

ipad be the inner padding (0x3636363636, one-block-long hexadecimal constant)

Then HMAC(K,m) is mathematically defined by HMAC(K,m) = H((K opad) H((Kipad) m)).

Assinaturas digitaisRecomenda-se a leitura deste documento: [www.pjvenda.net/papers/acrypto/public-key-security-paper.pdf]

Uma assinatura digital um tipo especfico de MAC que resulta de sistemas de criptografiaassimtrica, o RSA por exemplo, e usado para proteger a informao. Para assinar umamensagem, uma funoMessage Digest(MD) usada para processar o documento,produzindo um pequeno pedao de dados, chamado de hash.

Funes MD so mais parecidas com checksums quanto a no receber uma chave comoparte de sua entrada. Na verdade, entra-se com os dados a serem "digeridos" e o algoritmoMD gera um hash de 128 ou 160 bits (dependendo do algoritmo, so exemplos: MD4,MD5 e Snefru). Uma vez computada uma message digest, criptografa-se o hash geradocom uma chave privada. O resultado de todo este procedimento chamado de assinaturadigital da informao. A assinatura digital uma garantia que o documento uma cpiaverdadeira e correta do original.

O motivo para se usar funes message digestest diretamente ligado ao tamanho do blocode dados a ser criptografado para se obter a assinatura. De fato, criptografar mensagenslongas pode durar muito tempo, enquanto que criptografarhashs, que so blocos de dados

pequenos e de tamanho fixo, gerados pela MD torna o processamento mais eficiente.

Contudo, a simples presena de uma assinatura digital no documento no quer dizer nada.Assinaturas digitais, como outras convencionais, podem ser forjadas. A diferena que aassinatura digital pode ser matematicamente verificada. Dado um documento e suaassinatura digital, pode-se facilmente verificar sua integridade e autenticidade. Primeiro,executa-se a funo MD (usando o mesmo algoritmo MD que foi aplicado ao documento naorigem), obtendo assim um hash para aquele documento, e posteriormente, decifra-se aassinatura digital com a chave pblica do remetente. A assinatura digital decifrada deveproduzir o mesmo hash gerado pela funo MD executada anteriormente. Se estes valoresso iguais determinado que o documento no foi modificado aps a assinatura do mesmo,

caso contrrio o documento ou a assinatura, ou ambos foram alterados. Infelizmente, aassinatura digital pode dizer apenas que o documento foi modificado, mas no o que foimodificado e o quanto foi modificado. Todo o processo de gerao e verificao deassinatura digital pode ser visto na figura abaixo, utilizando o algoritmo de criptografia dechave pblica RSA.
http://www.pjvenda.net/papers/acrypto/public-key-security-paper.pdfhttp://www.pjvenda.net/papers/acrypto/public-key-security-paper.pdfhttp://www.pjvenda.net/papers/acrypto/public-key-security-paper.pdfhttp://www.pjvenda.net/papers/acrypto/public-key-security-paper.pdf


27/62

Para ser possvel que um documento ou uma assinatura adulterada no seja detectada, oatacante deve ter acesso a chave privada de quem assinou esse documento.

O que faz assinaturas digitais diferentes de MACs que enquanto estes ltimos requeremchaves privadas para verificao, assinaturas digitais so possveis de serem verificadasusando chaves pblicas.

A assinatura digital tambm valiosa pois pode-se assinar informaes em um sistema decomputador e depois provar sua autenticidade sem se preocupar com a segurana dosistema que as armazena.

Propriedades a verificar

Autenticidade - quem assinou identificado unicamente pela assinatura.

No-forjamento - quem assinou o proprio e fiz o deliberadamente.

Integridade - uma assinatura correcta em um documento garante que este no alteravelsem ser detectado.

No-reutilizao - a assinatura ou parte de documento no reutilizavel em outrodocumento.

No-repudio - o assinante no pode negar a sua assinatura.

Assinatura arbitrada

Envolve um arbitro que age como um mediador de confiana. Toda gente tem confiana noarbitro que pode ou no ver a mensagem. Usualmente baseam-se na criptografia simetrica.O arbitro unico ponto de falha.

Propriedades


28/62

autenticidade no-forjamento integridade no-reutilizao no-repudio

Assinatura directa

Envolve apenas o emissor e o receptor. O receptor deve ter acesso a chave publica doemissor (para verificar a sua assinatura). Usualmente baseada em criptografia assimetrica.

Propriedades

autenticidade no-forjamento integridade

no-repudio no garante a no-reutilizao

DSA/DSS

um algoritmo pblico. Parte do Digital Signature Standard (DSS). Recomendado paraaplicaes que requeiram assinatura digital ao invs da escrita. No pode ser usado paraencriptao por chave privada pois desencriptado pela chave pblica. A mensagem submetida ao algoritmo SHA que gera um hash da mensagem. Esse hash submetido aoalgoritmo DSA usando a chave privada do remetente; ao final temos a mensagem assinada.O remetente submete a mensagem recebida ao SHA para gerar o hash, usa a chave pblica

do remetente para decriptar a assinatura digital e compara o hash das mensagens. Se foremos mesmos, a mensagem autntica. Usa chaves de 512 bits a 128 bits.

Autoridade certificadoraA certificate authority orcertification authority (CA) is an entity that issues digitalcertificates for use by other parties. It is an example of a trusted third party. CAs arecharacteristic of many public key infrastructure (PKI) schemes.

Commercial CAs charge to issue certificates that will automatically be trusted by most webbrowsers (Mozilla maintains a list of at least 36 trusted root CAs, though multiple

commercial CAs or their resellers may share the same trusted root).http://en.wikipedia.org/wiki/Certification_authority - cite_note-0The number of webbrowsers and other devices and applications that trust a particular certificate authority isreferred to as ubiquity.

Aside from commercial CAs, some providers issue digital certificates to the public at nocost. Large institutions or government entities may have their own CAs.
http://en.wikipedia.org/wiki/Certification_authority#cite_note-0http://en.wikipedia.org/wiki/Certification_authority#cite_note-0http://en.wikipedia.org/wiki/Certification_authority#cite_note-0


29/62

A CA issues digital certificates that contain a public key and the identity of the owner.When an end-user tries to access an unknown URL, the web browser (e.g. Mozilla Firefoxand Microsoft Internet Explorer) will contact the CA to confirm the public key of the URL.The matching private key is not similarly made available publicly, but kept secret by theend user who generated the key pair. The certificate is also a confirmation or validation by

the CA that the public key contained in the certificate belongs to the person, organization,server or other entity noted in the certificate. A CA's obligation in such schemes is to verifyan applicant's credentials, so that users and relying parties can trust the information in theCA's certificates. CAs use a variety of standards and tests to do so. In essence, theCertificate Authority is responsible for saying "yes, this person is who they say they are,and we, the CA, verify that".

If the user trusts the CA and can verify the CA's signature, then he can also verify that acertain public key does indeed belong to whoever is identified in the certificate.

X.509

In the X.509 system, a Certification Authority issues a certificate binding a public key to aparticularDistinguished Name in the X.500 tradition, or to anAlternative Name such as ane-mail address or a DNS-entry.

An organization's trusted root certificates can be distributed to all employees so that theycan use the company PKI system. Browsers such as Internet Explorer, Netscape/Mozilla,Opera, Safari and Chrome come with root certificates pre-installed, so SSL certificatesfrom larger vendors will work instantly; in effect the browsers' developers determine whichCAs are trusted third parties for the browsers' users.

X.509 also includes standards for certificate revocation list (CRL) implementations, anoften neglected aspect of PKI systems. The IETF-approved way of checking a certificate'svalidity is the Online Certificate Status Protocol (OCSP). Firefox 3 enables OCSP checkingby default along with versions of Windows including Vista and later.

Structure of a certificate

The structure of an X.509 v3 digital certificate is as follows:

Certificateo Versiono Serial Numbero Algorithm IDo Issuero Validity

Not Before Not After

o Subjecto Subject Public Key Info


30/62

Public Key Algorithm Subject Public Key

o Issuer Unique Identifier (Optional)o Subject Unique Identifier (Optional)o Extensions (Optional)

... Certificate Signature Algorithm Certificate Signature

Issuer and subject unique identifiers were introduced in Version 2, Extensions in Version 3.Nevertheless, the Serial number must be unique for each certificate issued by a specific CA(as mentioned in RFC 2459).

Sample X.509 certificates

Ver [http://en.wikipedia.org/wiki/X.509]

Self-signed certificate

A self-signed certificate is an identity certificate that is signed by its own creator. That is,the person that created the certificate also signed off on its legitimacy.

In typical public key infrastructure (PKI) arrangements, that a particular public keycertificate is valid (i.e., contains correct information) is attested by a digital signature froma certificate authority (CA). Users, or their software on their behalf, check that the privatekey used to sign some certificate matches the public key in the CA's certificate. Since CAcertificates are often signed by other, "higher ranking," CAs, there must necessarily be ahighest CA, which provides the ultimate in attestation authority in that particular PKIscheme.

Obviously, the highest-ranking CA's certificate can't be attested by some other higher CA(there being none), and so that certificate can only be "self-signed." Such certificates arealso termed root certificates. Clearly, the lack of mistakes or corruption in the issuance ofsuch certificates is critical to the operation of its associated PKI; they should be, andgenerally are, issued with great care.

In a web of trust certificate scheme there is no central CA, and so identity certificates foreach user can be self-signed. In this case, however, it has additional signatures from otherusers which are evaluated to determine whether a certificate should be accepted as correct.

So, if users Bob, Carol, and Edward have signed Alice's certificate, user David may decideto trust that the public key in the certificate is Alice's (all these worthies having agreed bytheir signatures on that claim). But, if only user Bob has signed, David might (based on hisknowledge of Bob) decide to take additional steps in evaluating Alice's certificate. On theother hand, Edward's signature alone on the certificate may by itself be enough for David totrust that he has Alice's public key (Edward being known to David to be a reliably carefuland trustworthy person). There is of course, a potentially difficult regression here, as howcan David know that Bob, Carol, or Edward have signed any certificate at all unless he
http://en.wikipedia.org/wiki/X.509http://en.wikipedia.org/wiki/X.509


31/62

knows their public keys (which of course came to him in some sort of certificate)? In thecase of a small group of users who know one another in advance and can meet in person(e.g., a family), users can sign one another's certificates when they meet as a group, but thissolution does not scale to larger settings. This problem is solved by fiat in X.509 PKIschemes as one believes (i.e., trusts) the root certificate by definition. The problem of

trusting certificates is real in both approaches, but less easily lost track of by users in a Webof Trust scheme.

Centro de distribuio de chaves (KDC)A key distribution center (KDC) is part of a cryptosystem intended to reduce the risksinherent in exchanging keys. KDCs often operate in systems within which some users mayhave permission to use certain services at some times and not at others.

For instance, an administrator may have established a policy that only certain users may usethe tape backup facility. (Perhaps the administrator has concerns that unrestricted use might

result in someone smuggling out a tape containing important information; but the precisereason does not matter for the purpose of explaining the functioning of the key distributioncenter.) Many operating systems can control access to the tape facility via a 'systemservice'. If that system service further restricts the tape drive to operate on behalf only ofusers who can submit a service-granting ticket when they wish to use it, there remains onlythe task of distributing such tickets to the appropriately permitted users. If the ticketconsists of (or includes) a key, we can then term the mechanism which distributes it a KDC.Usually, in such situations, the KDC itself also operates as a system service.

Assinatura cega

A blind signature, is a form of digital signature in which the content of a message isdisguised before it is signed. The resulting blind signature can be publicly verified againstthe original, unblinded message in the manner of a regular digital signature. Blindsignatures are typically employed in privacy-related protocols where the signer andmessage author are different parties. Examples include cryptographic election systems anddigital cash schemes.

An often-used analogy to the cryptographic blind signature is the physical act of enclosinga message in a special write-through-capable envelope, which is then sealed and signed bya signing agent. Thus, the signer does not view the message content, but a third party canlater verify the signature and know that the signature is valid within the limitations of the

underlying signature scheme.

Blind signatures can also be used to provide unlinkability, which prevents the signer fromlinking the blinded message it signs to a later un-blinded version that it may be called uponto verify. In this case, the signer's response is first "un-blinded" prior to verification in sucha way that the signature remains valid for the un-blinded message. This can be useful inschemes where anonymity is required.


32/62

Blind signature schemes can be implemented using a number of common public keysigning schemes, for instance RSA and DSA. To perform such a signature, the message isfirst "blinded", typically by combining it in some way with a random "blinding factor". Theblinded message is passed to a signer, who then signs it using a standard signing algorithm.The resulting message, along with the blinding factor, can be later verified against the

signer's public key. In some blind signature schemes, such as RSA, it is even possible toremove the blinding factor from the signature before it is verified. In these schemes, thefinal output (message/signature) of the blind signature scheme is identical to that of thenormal signing protocol.

Blind signature schemes exist for many public key signing protocols. Some examples areprovided below. In each example, the message to be signed is contained in the value m. m isconsidered to be some legitimate input to the signature function. As an analogy, considerthat Alice has a letter which should be signed by an authority (say Bob), but Alice does notwant to reveal the content of the letter to Bob. She can place the letter in an envelope linedwith carbon paper and send it to Bob. Bob will sign the outside of the carbon envelopewithout opening it and then send it back to Alice. Alice can then open it to find the lettersigned by Bob, but without Bob having seen its contents.

More formally a blind signature scheme is a cryptographic protocol that involves twoparties, a user Alice that wants to obtain signatures on her messages, and a signer Bob thatis in possession of his secret signing key. At the end of the protocol Alice obtains asignature on m without Bob learning anything about the message. This intuition of notlearning anything is hard to capture in mathematical terms. The usual approach is to showthat for every (adversarial) signer, there exists a simulator that can output the sameinformation as the signer. This is similar to the way zero-knowledge is defined in zero-knowledge proof systems.

Blind RSA signatures

One of the simplest blind signature schemes is based on RSA signing. A traditional RSAsignature is computed by raising the message m to the secret exponent dmodulo the publicmodulusN. The blind version uses a random value r, such that ris relatively prime toN(i.e.gcd(r,N) = 1). ris raised to the public exponent e moduloN, and the resulting value

remodNis used as a blinding factor. The author of the message computes the product ofthe message and blinding factor, i.e.

and sends the resulting value m' to the signing authority. Because ris a random value andthe mapping is a permutation it follows that remodNis random too. Thisimplies that m' does not leak any information about m. The signing authority then calculatesthe blinded signatures'as:

s'is sent back to the author of the message, who can then remove the blinding factor to


33/62

reveals, the valid RSA signature ofm:

This works because RSA keys satisfy the equation and thus

hences is indeed the signature ofm.

Dangers of blind signing

RSA is subject to the RSA blinding attack through which it is possible to be tricked intodecrypting a message by blind signing another message. Since the signing process isequivalent to decrypting with the signers secret key, an attacker can provide a blindedversion of a message m encrypted with the signers public key, m' for them to sign. Theencrypted message would usually be some secret information which the attacker observed

being sent encrypted under the signers public key which the attacker wants to learn. Whenthe attacker unblinds the signed version they will have the clear text:

where m' is the encrypted version of the message. When the message is signed, the cleartextm is easily extracted:

Note that (n) refers to Euler's totient function. The message is now easily obtained.

This attack works because in this blind signature scheme the signer signs the messagedirectly. By contrast, in an unblinded signature scheme the signer would typically use apadding scheme (e.g. by instead signing the result of a Cryptographic hash function appliedto the message, instead of signing the message itself), however since the signer does notknow the actual message, any padding scheme would produce an incorrect value whenunblinded. Due to this multiplicative property of RSA, the same key should never be usedfor both encryption and signing purposes.


34/62

Zero-knowledge

A zero-knowledge prooforzero-knowledge protocol is an interactive method for oneparty to prove to another that a (usually mathematical) statement is true, without revealinganything other than the veracity of the statement.

Abstract example

It is common practice to label the two parties in a zero-knowledge proof as Alice (theprover of the statement) and Bob (the verifier of the statement).

In this story, Alice has uncovered the secret word used to open a magic door in a cave. Thecave is shaped like a circle, with the entrance on one side and the magic door blocking theopposite side. Bob says he'll pay her for the secret, but not until he's sure that she reallyknows it. Alice says she'll tell him the secret, but not until she receives the money. Theydevise a scheme by which Alice can prove that she knows the word without telling it toBob.

First, Bob waits outside the cave as Alice goes in. We label the left and right paths from theentrance A and B. She randomly takes either path A or B. Then, Bob enters the cave andshouts the name of the path he wants her to use to return, either A or B, chosen at random.Providing she really does know the magic word, this is easy: she opens the door, ifnecessary, and returns along the desired path. Note that Bob does not know which path shehas gone down.

However, suppose she did not know the word. Then, she would only be able to return bythe named path if Bob were to give the name of the same path that she had entered by.Since Bob would choose A or B at random, he would have a 50% chance of guessing

correctly. If they were to repeat this trick many times, say 20 times in a row, her chance ofsuccessfully anticipating all of Bob's requests would become vanishingly small.

Thus, if Alice reliably appears at the exit Bob names, he can conclude that she is very likelyto know the secret word.

Definition

A zero-knowledge proof must satisfy three properties:

1. Completeness: if the statement is true, the honest verifier (that is, one following the

protocol properly) will be convinced of this fact by an honest prover.2. Soundness: if the statement is false, no cheating prover can convince the honest

verifier that it is true, except with some small probability.3. Zero-knowledge: if the statement is true, no cheating verifier learns anything other

than this fact. This is formalized by showing that every cheating verifier has somesimulatorthat, given only the statement to be proven (and no access to the prover),can produce a transcript that "looks like" an interaction between the honest proverand the cheating verifier.


35/62

The first two of these are properties of more general interactive proof systems. The third iswhat makes the proof zero-knowledge.

Zero-knowledge proofs are not proofs in the mathematical sense of the term because thereis some small probability, thesoundness error, that a cheating prover will be able to

convince the verifier of a false statement. In other words, they are probabilistic rather thandeterministic. However, there are techniques to decrease the soundness error to negligiblysmall values.

A formal definition of zero-knowledge has to use some computational model, the mostcommon one being that of a Turing machine. LetP,V, and Sbe turing machines. Aninteractive proof system with (P,V) for a languageL is zero-knowledge if for any

probabilistic polynomial time (PPT) verifier there exists an expected PPT simulatorSsuch that

The proverPis modeled as having unlimited computation power (in practice, P usually is aProbabilistic Turing machine). Intuitively, the definition states that an interactive proof

system (P,V) is zero- knowledge if for any verifier there exists an efficient simulatorS

that can reproduce the conversation betweenPand on any given input. The auxiliary

stringzin the definition plays the role of prior knowledge. The definition implies thatcannot use any prior knowledge stringzto mine information out of its conversation withPbecause we demand that ifSis also given this prior knowledge then it can reproduce the

conversation between andPjust as before.The definition given is that of perfect zero-knowledge. Computational zero-knowledge is

obtained by requiring that the views of the verifier and the simulator are only

computational indistinguishable, given the auxiliary string.Practical example

We can extend these ideas to a more realistic cryptography application. In this scenario,Alice knows a Hamiltonian cycle for a large graph, G. Bob knows G but not the cycle (e.g.,Alice has generated G and revealed it to him.) Alice will prove that she knows the cyclewithout revealing it. A Hamiltonian cycle in a graph is just one way to implement a zeroknowledge proof; in fact any NP-complete problem can be used, as well as some otherdifficult problems such as factoring. However, Alice does not want to simply reveal theHamiltonian cycle or any other information to Bob; she wishes to keep the cycle secret(perhaps Bob is interested in buying it but wants verification first, or maybe Alice is the

only one who knows this information and is proving her identity to Bob).

To show that Alice knows this Hamiltonian cycle, she and Bob play several rounds of agame.

At the beginning of each round, Alice createsH, an isomorphic graph to G (i.e.Hisjust like G except that all the vertices have different names). Since it is trivial totranslate a Hamiltonian cycle between isomorphic graphs with known isomorphism,


36/62

if Alice knows a Hamiltonian cycle forG she also must know one forH. Alice commits toH. She could do so by using a cryptographic commitment scheme.

Alternatively, she could number the vertices ofH, then for each edge ofHwrite asmall piece of paper containing the two vertices of the edge and then put thesepieces of paper upside down on a table. The purpose of this commitment is that

Alice is not able to changeHwhile at the same time Bob has no information aboutH. Bob then randomly chooses one of two questions to ask Alice. He can either ask her

to show the isomorphism betweenHand G (see graph isomorphism problem), or hecan ask her to show a Hamiltonian cycle inH.

If Alice is asked to show that the two graphs are isomorphic, she first uncovers allofH(e.g. by turning all pieces of papers that she put on the table) and then providesthe vertex translations that map G toH. Bob can verify that they are indeedisomorphic.

If Alice is asked to prove that she knows a Hamiltonian cycle inH, she translatesher Hamiltonian cycle in G ontoHand only uncovers the edges on the Hamiltoniancycle. This is enough for Bob to check thatHdoes indeed contain a Hamiltoniancycle.

Completeness:

During each round, Alice does not know which question she will be asked until after givingBobH. Therefore, in order to be able to answer both, Hmust be isomorphic to G and shemust have a Hamiltonian cycle inH. Because only someone who knows a Hamiltoniancycle in G would always be able to answer both questions, Bob (after a sufficient numberof rounds) becomes convinced that Alice does know this information.

Zero-Knowledge:

Alice's answers do not reveal the original Hamiltonian cycle in G. Each round, Bob willlearn onlyH's isomorphism to G or a Hamiltonian cycle inH. He would need both answersfor a singleHto discover the cycle in G, so the information remains unknown as long asAlice can generate a uniqueHevery round. If Alice does not know of a Hamiltonian Cyclein G, but somehow knew in advance what Bob would ask to see each round then she couldcheat. For example, if Alice knew ahead of time that Bob would ask to see the HamiltonianCycle inHthen she could generate a Hamiltonian cycle for an unrelated graph. Similarly, ifAlice knew in advance that Bob would ask to see the isomorphism then she could simplygenerate an isomorphic graphH(in which she also does not know a Hamiltonian Cycle).Bob could simulate the protocol by himself (without Alice) because he knows what he willask to see. Therefore, Bob gains no information about the Hamiltonian cycle in G from theinformation revealed in each round.


37/62

Soundness:

If Alice does not know the information, she can guess which question Bob will ask andgenerate either a graph isomorphic to G or a Hamiltonian cycle for an unrelated graph, butsince she does not know a Hamiltonian cycle forG she cannot do both. With this

guesswork, her chance of fooling Bob is 2n, where n is the number of rounds. For allrealistic purposes, it is infeasibly difficult to defeat a zero knowledge proof with areasonable number of rounds in this way.

Variants of zero-knowledge

Different variants of zero-knowledge can be defined by formalizing the intuitive concept ofwhat is meant by the output of the simulator "looking like" the execution of the real proofprotocol in the following ways:

We speak ofperfect zero-knowledge if the distributions produced by the simulatorand the proof protocol are distributed exactly the same. This is for instance the casein the first example above.

Statistical zero-knowledge means that the distributions are not necessarily exactlythe same, but they are statistical close, meaning that their statistical difference is anegligible function.

We speak ofcomputational zero-knowledge if no efficient algorithm can distinguishthe two distributions.

Applications

Research in zero-knowledge proofs has been motivated by authentication systems whereone party wants to prove its identity to a second party via some secret information (such asa password) but doesn't want the second party to learn anything about this secret. This iscalled a "zero-knowledge proof of knowledge". However, a password is typically too smallor insufficiently random to be used in many schemes for zero-knowledge proofs ofknowledge. A zero-knowledge password proof is a special kind of zero-knowledge proof ofknowledge that addresses the limited size of passwords.

One of the most fascinating uses of zero-knowledge proofs within cryptographic protocolsis to enforce honest behavior while maintaining privacy. Roughly, the idea is to force a userto prove, using a zero-knowledge proof, that its behavior is correct according to the

protocol. Because of soundness, we know that the user must really act honestly in order tobe able to provide a valid proof. Because of zero knowledge, we know that the user doesnot compromise the privacy of its secrets in the process of providing the proof. Thisapplication of zero-knowledge proofs was first used in the ground-breaking paper ofGoldreich, Micali, and Wigderson on secure multiparty computation.


38/62

Dinheiro digitalEssentially, digital cash mimics the functionality of paper cash. More technically, digitalcash is a payment message bearing a digital signature which functions as a medium ofexchange or store of value. Paper currency and coins represent value because they arebacked by a trusted third party, the government and the banking industry. Digital coins willalso represent value because they are backed by a trusted third party, usually a bank that iswilling to convert digital cash to physical cash.

How does Digital Cash work?

There are a number of electronic cash protocols. To a degree, all digital cash schemesoperate in the following manner: A user installs a "cyber wallet" onto computer. Money canbe put in the wallet by deciding how much is needed and then sending an encryptedmessage to the bank asking for this amount to be deducted from the user's account. Thebank reads the message with private key decryption and verifies if it has been digitallysigned in order to identify the user. The bank then generates "serial numbers", encrypts themessage, signs it with its digital signature and returns it. The user is now entitled to use themessage (coin or token) to spend it at merchant sites. Merchants receive e-cash during a

transaction and see that it has been authorized by a bank. They then contact the bank tomake sure the coins have not been spent somewhere else, and the amount is credited to themerchant's account.

Key Properties of a Private Digital Cash System

The use of digital cash is not dependent on any physical location, and can be transferredbetween the physical world and virtual world of the Internet Smart card integration with


39/62

computer networks have been proposed to offer this functionality. Real cash is limited byits physical form .Cash represented by streams of 0's and 1's can take advantage of itselectronic nature, and permeate through networks and digital sale devices at light-speed,worldwide.

Ideal properties:Secure. The transaction protocol must ensure that a high-level security is maintainedthrough sophisticated encryption techniques. For instance, Alice should be able to passdigital cash to Bob without either of them, or others, able to alter or reproduce theelectronic token.

Anonymous. Anonymity assures the privacy of a transaction on multiple levels. Beyondencryption, this optional intractability feature of digital cash promises to be one of themajor points of competition as well as controversy between the various providers.Transactional privacy will also be at the heart of the government's attack on digital cash

because it is that feature which will most likely render current legal tender irrelevant. BothAlice and Bob should have the option to remain anonymous in relation to the payment.Furthermore, at the second level, they should have the option to remain completelyinvisible to the mere existence of a payment on their behalf.

Portable. The security and use of the digital cash is not dependent on any physicallocation. The cash can be transferred through computer networks and off the computernetwork into other storage devices. Alice and Bob should be able to walk away with theirdigital cash and transport it for use within alternative delivery systems, including non-computer-network delivery channels. Digital wealth should not be restricted to a unique,proprietary computer network.

Two-way. The digital cash can be transferred to other users. Essentially, peer-to-peerpayments are possible without either party required to attain registered merchant status aswith today's card-based systems. Alice, Bob, Carol, and David share an elaborate dinnertogether at a trendy restaurant and Alice pays the bill in full. Bob, Carol, and David eachshould then be able to transfer one-fourth of the total amount in digital cash to Alice.

Off-line capable. The protocol between the two exchanging parties is executed off-line,meaning that neither is required to be host-connected in order to process. Availability mustbe unrestricted. Alice can freely pass value to Bob at any time of day without requiringthird-party authentication.

Wide acceptability. The digital cash is well-known and accepted in a large commercialzone. Primarily a brand issue, this feature implies recognition of and trust in the issuer.With several digital cash providers displaying wide acceptability, Alice should be able touse her preferred unit in more than just a restricted local setting.


40/62

Comunicao seguraWhen two entities are communicating with each other, and they do not want a third party tolisten to their communication, then they want to pass on their message in such a way that nobody else could understand their message. This is known as communicating in a secure

manner orsecure communication. Secure communication includes means by whichpeople can share information with varying degrees of certainty that third parties cannotknow what was said. Other than communication spoken face to face out of possibility oflistening, it is probably safe to say that no communication is guaranteed secure in thissense, although practical limitations such as legislation, resources, technical issues(interception and encryption), and the sheer volume of communication are limiting factorsto surveillance.

The purpose of this article is to describe the various means by which security is sought andcompromised, the differing kinds of security possible, and the current means and theirdegree of security readily available.

With many communications taking place over long distance and mediated by technology,and increasing awareness of the importance of interception issues, technology and itscompromise are at the heart of this debate. For this reason, this article focusses oncommunications mediated or intercepted by technology.

Also see Trusted Computing, an approach under present development that achieves securityin general at the potential cost of compelling obligatory trust in corporate and governmentalbodies.

Canal seguro

A secure channel is a way of transferring data that is resistant to interception andtampering. A confidential channel is a way of transferring data that is resistant tointerception, but not necessarily resistant to tampering. An authentic channel is a way oftransferring data that is resistant to tampering but not necessarily resistant to interception.

Secure channels in the real world

There are no perfectly secure channels in the real world. There are, at best, only ways tomake insecure channels (eg, couriers, homing pigeons, diplomatic bags, etc) less insecure:padlocks (between courier wrists and a briefcase), loyalty tests, security investigations, andguns for co

apontamentos de seguranca

Documents