Cryptography-Digest Digest #131, Volume #14 Thu, 12 Apr 01 22:13:00 EDT
Contents:
Re: Crypto Books (David A Molnar)
MD5 flaws (miathan)
Ethernet & Encryption ("Latyr Jean-Luc FAYE")
----------------------------------------------------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Crypto Books
Date: 13 Apr 2001 00:03:34 GMT
David M. Jones <[EMAIL PROTECTED]> wrote:
> Arto Salomaa. Public-Key Cryptography, second edition. Springer,
> 1996. 3-540-61356-0.
> I have a chance to pick it up cheap. Is it worth it?
I keep coming back to it in the library (it's in Cabot library at Harvard if
you want to take a look and happen to be nearby) because it has a nice
section on "alternative bases for public-key cryptosystems." This includes
material on automata-based PKCs which is hard to find otherwise.
I haven't carefully evaluated the rest of the book. From short browsing it
strikes me as "Applied Cryptography with more rigour" -- i.e. a level of
math maturity lower than Koblitz but not afraid to give actual details. Wish
I'd known about it four years ago. Has a similar topics list to Applied
Crypto, as well, including a nice section on voting protocols.
There was one odd thing - he talks about the importance of chosen-ciphertext
attack, but doesn't use the term "chosen-ciphertext attack." Instead, there
is a "Legal World" section in the discussion of a cryptosystem in which
everyone behaves as expected, and then Salomaa discusses the evil things
that could happen if people don't behave as in the "Legal World."
Perhaps this is because when the book was first written (I think in 1988??)
terms weren't widespread or standardized. Maybe it's a language thing. In
any case, I found it a little jarring but would probably have gotten used to
it quickly if I'd actually been reading carefully.
I would pick it up if I could get it cheap...but then again, I'd pick up
most crypto books.
-David
------------------------------
From: miathan <[EMAIL PROTECTED]>
Subject: MD5 flaws
Date: Fri, 13 Apr 2001 01:26:32 GMT
Hello all...
I keep encountering mentions of those supposed security flaws in MD5 in
variuous documents, but seem unable to find what exactly those are.
Does anyone know a document describing them and how serious the problems
are?
I'm sorry if this is a F.A.Q. but didn't see such a topic here
greetings..
miathan
------------------------------
From: "Latyr Jean-Luc FAYE" <[EMAIL PROTECTED]>
Subject: Ethernet & Encryption
Date: Fri, 13 Apr 2001 02:57:42 +0100
Dear all,
You will find below the report of an assignement I had done.
I would like to have your comments on the solution I proposed on DES and
RSA, the weakness of the system and the improvements that can be made.
Thanks in advance.
Regards
Jean-Luc
=================
Introduction
The objective of this assignment is to gain a detailed understanding of the
different sub system/elements that need to be incorporated into a system
which would perform a link level encryption. A functional specification of a
link level encryption system that will provide secure transmission over an
Ethernet network will be built to fill this need.
A brief presentation of Ethernet and its currant security will in a first
time be done. Then, we will see what requirements the system needs to
fulfil, the overall architecture that the system needs. The problem of key
management will also be seen as well as the special computation
requirements, the generation of random numbers that will be required and any
points of weakness the system may have.
1) The Ethernet
Ethernet was originally developed by Xerox in the late 1970. It is a type of
network cabling and signalling specifications (OSI Model layers 1 and 2). It
was originally an improvement on the Aloha system of arbitrating access to a
shared communications channel. The Ethernet has a mechanism that detects
when a collision occurs (collision detect), includes "listen before talk,"
in which stations listen for activity (carrier sense) before transmitting,
and supports access to a shared channel by multiple stations (multiple
access). It is easy to understand why the Ethernet channel access protocol
is called Carrier Sense Multiple Access with Collision Detect (CSMA/CD).
Formal specifications for Ethernet were published in 1980 by a multi-vendor
consortium that created the DEC-Intel-Xerox (DIX) standard which made
Ethernet an open, production-quality system that operates at 10-Mbps.
Ethernet technology was then adopted for standardization by the LAN
standards committee of the Institute of
Electrical and Electronics Engineers (IEEE 802). The IEEE standard has since
been
adopted by the International Organization for Standardization (ISO), which
makes it a worldwide networking standard.
The Ethernet system consists of three basic elements:
1. the physical medium used to carry Ethernet signals between computers,
2. a set of medium access control rules embedded in each Ethernet interface
that allow multiple computers to fairly arbitrate access to the shared
Ethernet channel, and
3. an Ethernet frame that consists of a standardized set of bits used to
carry data over the system.
Each Ethernet-equipped computer, also known as a station, operates
independently of all other stations on the network: there is no central
controller. All stations attached to an Ethernet are connected to a shared
signalling system, also called the medium. Ethernet signals are transmitted
serially, one bit at a time, over the shared signal channel to every
attached station. To send data a station first listens to the channel, and
when the channel is idle the station transmits its data in the form of an
Ethernet frame, or packet.
The data exchanged between nodes are put in standardised packets, which
contain several fields:
Preamble|Start|Destination|Source|Length/Type| Data |Check
62bits 2bits 6bytes 6bytes 2bytes 46bytes to 4bytes 1.5 Kbytes
Preamble: Serie of 1s and 0s used to achieve bit synchronisation.
Start of frame delimiter: two consecutive 1s used to achieve byte alignment.
Destination Ethernet address: Address of intended receiver.
Source Ethernet address: Address of the sending station.
Length or type field: Either the number of bytes of data or the type of
packet depending if you are using IEEE 802.3 or Ethernet I&II protocol.
Data: Data sent. Short packets must be padded to 46 bytes.
Frame Check Sequence: A CRC on 32 bits.
To communicate with each other, the frames produce Ethernet frames, which
are carried over the whole channel to each node. Then each node reads the
header to see if the destination address is theirs. If it is not, it ignores
the frame and starts listening again. If it is, the node recovers the frame
and reads the data it contains.
Knowing this, it is easy to see there is no security on Ethernet. Any node
can pretend it is the destination node and read the data all the other nodes
will send without the other nodes ever knowing this. There is no security
service concerning the exchange of data. We will try to implement one by
encrypting the data sent by the nodes.
2) Conditions that should be met
To make the exchange of data secure, the following conditions should be met:
- The system must provide authentication and confidentiality
- The system should not slow down the exchange of data noticeably
- Only the data field of the frame must be encrypted as all the other parts
should be able to be read by all the other nodes, especially the destination
node field.
- The encryption functions will be at link level
- The cost of the system is not a factor
- The security service is between machines, not users
As our report must be short, we will not give the algorithms of the
different methods of encryption that will we use in the design of the
system. These algorithms can be found easily on Internet or in the notes of
the course.
3) The architecture of the system
The data needs to be encrypted to have a secure transmission over Ethernet.
In secure, we mean that the confidentiality of the message and the
authentication of the sender must be fulfilled. As the load of data carried
across the Ethernet is heavy, the encryption scheme must be computationally
very fast. These are the first two conditions that we have talked about
above. Because of its rapidity in computation and its good level of
confidentiality and authentication, DES has been chosen to do the
conventional data encryption.
1. DES for data encryption
As we have a block-oriented transmission, the mode of operation the most fit
to our case would be the CBC (Cipher Block Chaining) mode. It will be
implemented at the data link level at each node of the network. Each node
has to be able to encrypt and decrypt the data.
The way DES works is that when a node wants to send data to another node, it
has to encrypt the data with a 56 bit secret key it will have generated
randomly. The key will encrypt the data in 64 bit blocks using the DES
algorithm. The 64 bit blocks will then be embedded in the Ethernet frame and
sent on the network. The receiver node will then use the same secret key to
decrypt the data and read it. The secret key thus needs to be known by the
sending and receiving node.
Here is a quick scheme of how the transmission is done:
data Cipher data
Sending Encryption Decryption Receiving
Node algorithm algorithm Node
The sending node and the receiving node share the same secret key as it is
needed and used to encrypt and decrypt the data. As the secret key cannot be
constant and is changed at each data transmission, a public key encryption
is needed to transmit the new secret key each time data is transmitted. The
public key encryption involves no third party, as a distribution center, is
used to distribute the key as the secret key is generated by the sending
node and delivered to the receiving node. As no third party is involved, it
is more secure and less traffic is involved ,as the sending node just sends
the key compared to the case where the distribution center would need to
send the key to both nodes. Less traffic means less occasions to intercept
the key.
When the data transmission is finished, the secret key is erased from both
the nodes. If the nodes want to communicate again, a new secret key will be
generated from the sending node and sent to the receiving node. The same
secret key is never used twice. This makes any attempt of a brute-force
attack impractical knowing the level of security of the DES encrypting
algorithm.
2. RSA for key exchange
We have decided to use RSA for the key exchange as the computation needed
for the calculation of the secret key is not too heavy for a node, and that
a third party was thus not necessary and not wished for the reason explained
above. The Diffie-Hellman algorithm was not used even if it was more secure
than RSA because it does not provide the authentication check of the two
nodes before the exchange of the key. Indeed, it considers that the sender
and the receiver are what they say they are, which is not always our case.
There fore, RSA will be used to do the exchange of the secret keys.
Public key algorithm, contrarily to conventional single key encryption,
involves the use of two keys. Indeed it needs to be more secure as the
security of the rest of the data transfer relies on it. The processing power
required is, however, much more important, which makes it inadapted for the
data encryption. While the data load needed to encrypt two keys is
acceptable, it would not be to encrypt data, which is much more voluminous.
We will use public key algorithm to exchange the secret keys used to encrypt
the data, as it also provides digital signature. With RSA, either of the two
keys can be used to encrypt or decrypt with the other decrypting or
encrypting. There is no need to generate a second set of key if the
receiving node wishes to send something to the sending node.
Contrarily to DES, each node generates a pair of keys. It will publish its
encryption key or public key, so that everyone can see and use it, and keep
its companion key secret (private key). If the sending node, say node A,
wishes to send its secret data encryption key or secret conventional key
(SCK), to the receiving node B, it encrypts the SCK using node B's public
key K KUB. When B gets the encoded SCK, it decrypts it using its private key
KRB.
This ensures that only B can decrypt SCK as only B knows its secret key as
it has generated it and has sent it nowhere. Therefore not only the
confidentiality condition is fulfilled but we are also sure that it is B
that received the SCK because if it is not the node will not be able to
decrypt SCK.
To make sure that it is A who sent it, and fulfil the authentication
condition, A can encrypt the SCK with its private key (KRA) to have B
decrypt it with A's public key (KUA).
We can see that here, the SCK is first encoded using the sender A's private
key KRA , providing the digital signature. Then the second encryption is
performed using the receiver B's public key KUB , which ensures
confidentiality. The problem with this scheme is that the public-key
algorithm, which is computationally intensive, must be used four times:
twice for encryption and twice for decryption.
As security is wanted between machines and not users, the RSA keys do not
need to be changed at each end of session by a user. It is possible to keep
the keys for several sessions. Indeed, we can update the RSA keys after a
longer time, as RSA is very robust. It is really needed to change the keys
only once a day or for more security, several time a day. This reduces the
number of keys generated and used by the nodes of the Ethernet network.
Each node easily generates its public key and secret key using the RSA
algorithm when it wishes to communicate on the Ethernet but there is still
the problem of key distribution. Indeed, the sender node needs the public
key of the receiver node so it can encrypt the SCK and the receiver node
needs the sender's public key so it can decrypt the encrypted SCK.
3.Certification authority: exchange of public key
Several techniques are possible. The requirement in the choice of the best
of these techniques in the present case is that no node could pretend to be
another node.
One of the best solutions is to have an authority, a node that can be
trusted in the network because of different reasons, which will maintain a
dynamic directory with the public key of each node of the Ethernet. This
authority will also deliver certificates X.509 to enable the authentication
of all the nodes.
The process can be divided in two parts: first a registration sequence and
then a distribution sequence.
During registration, each node that wants to communicate with another
generates a new public key and sends it to the certification authority. The
certificate authority sends back to the node a signed certificate X.509.
This signature is actually an encryption with the private key of the
authority. The certificate contains the public key of the node, its period
of validity, the identity of the node and other information. This way, the
node can check that nobody has taken its identity to have access to its
certificate.
During the distribution of certificates phase, any node which wants to
obtain the public key of another node to send it data, or to decrypt the
data it has received, can recover the certificate of this node whom the
authenticity is certified by the authority. No party other than the
authority can modify the certificate as it is coded with the authority's
secret key.
It is only if, by someway, a node succeeds in stealing the authorities
private key that there can be problems. This case is very improbable.
We will assume that all the nodes know the public key of the certification
authority and only the authority knowing the corresponding private key.
Measures can be implemented to limit the amount of connections and data that
needs to be exchanged between a node and the authority. For example, we can
decide that each time a node asks the authority for the certificate and
public key of another node, the node saves the public key of the node it a
directory in the memory of the machine until the expiration date of the
validity of the certificate. This might bring problems if a public key has
to be changed before the end of the validity of its certificate, if a
private key has been compromised for example. Indeed, the certificate
authority would have to send an update of the certificate to all the nodes
that have kept the certificate in memory in this case. Therefore this might
not be such a bright idea, as it requires the certificate authority to store
which certificate was sent to which node and create a large data sent on the
network when it happens.
4) Special computation requirements
The single key of the DES algorithm is chosen randomly using a pseudo-random
numbers generator. This should not cause any kind of problems since it does
not need much computation.
The generation of the two pairs of keys for RSA involves much more
calculation. Indeed, for RSA, the calculation of large prime numbers is
done. To do this odd random numbers are generated. These numbers are then
tested to see if they are prime by using the Miller-Rabin scheme. This needs
much more computation as the scheme is done as many time as seems necessary
to have the assurance that the number is prime.
Therefore the encryption and decryption with the RSA algorithm requires a
high level of computation. The computers connected to the network have to be
sufficiently powerful to do this if we do not want reduce the number of time
the Miller-Rabin algorithm is applied, taking the risk that the odd number
is not prime, which would compromise the effectiveness of the algorithm and
thus, encryption.
5) Generation of random numbers
The generation of random numbers plays an important role in cryptography as
they are used in many algorithms. In our system, we use random numbers in
the generation of the conventional encryption key and in the generation of
the keys for the RSA public key algorithm.
Several random number generation methods are possible. The congruential
method will be our choice. It is the most widely used technique and it is
quite robust when implemented with appropriate values for the parameters.
Its robustness also comes from the cyclic encryption. The congruential
technique also has the advantage to need only a fair amount of computation
compared to other pseudorandom generators like ANSI X9.17, which requires
much more computation for an almost equal robustness.
6) Points of weakness
This system has several weaknesses.
- Indeed, even if we have tried to reduce the computations to the minimal
while keeping a good security, the distribution of session keys by
public-key encryption may hamper overall system performance because it still
needs a lot of computation power to do the public-key encrypting and
decrypting.
- We cannot encrypt the routing header of the packet to allow the nodes to
know which of them the packet is destined to without having all the nodes
decrypt the header. This means that even if the data is secured, the traffic
pattern is not. An enemy can have access to the header information and
counterfeit it without us knowing it.
- Hardware is necessary to provide to all the nodes of the network the
public key of the certification authority. Indeed the network cannot be used
as it is not safe and we cannot encrypt the key.
- Furthermore, even if it is not probable, should an enemy succeed in
getting the private key of the certification authority, the opponent would
be able to pass out counterfeit public-key and do about anything he wants.
Conclusion
The designed system provides the security services we wanted it to have:
confidentiality and authentication for the data exchanged over the network.
To do this, the system uses a combination of DES to encrypt the data and of
RSA to distribute the public key. The combination of the two is necessary,
as it would take too much time to use just the second just to improve
security.
Another feature of the system is that no session key exist before the start
of the exchange and none exist after it is finished, leaving no time for an
opponent to try to use it. Therefore the risks of compromising the key are
minimal and near impossible.
The weaknesses of this system will be found in all other systems that could
be built, as they are inherent to the Ethernet protocol.
---
Latyr Jean-Luc FAYE
http://faye.cjb.net
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
