Cryptography-Digest Digest #177, Volume #14 Wed, 18 Apr 01 16:13:00 EDT
Contents:
Re: Ethernet & Encryption ("Latyr Jean-Luc FAYE")
Re: There Is No Unbreakable Crypto (John Savard)
GSM Encryption and Authentication ("Erinn Looney-Triggs")
Re: "UNCOBER" = Universal Code Breaker ("M.S. Bob")
Re: I took the $5000 Goldman Challenge (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
From: "Latyr Jean-Luc FAYE" <[EMAIL PROTECTED]>
Subject: Re: Ethernet & Encryption
Date: Wed, 18 Apr 2001 20:19:09 +0100
>> The nodes do not have a central authority public key should they ?
>Then how can they authenticate messages they get from the central
authority? If
>they discover the authority across the network, and node can masquerade as
the
>authority and compromise the system.
>> If yes
>>can I imagine the same public key at the start is never use then all nodes
>> broadcast their own public key ?
>Please amplify/rephrase this question, as I don't know how to respond.
Hi folks
Thanks for all your suggestions. To solve the problems you raised up, now I
would like to know if I can use Diffie Hellman for key exchange rather than
RSA ???
What do you think about this option ?
Thanks
---
Latyr Jean-Luc FAYE
http://faye.cjb.net
"Latyr Jean-Luc FAYE" <[EMAIL PROTECTED]> a �crit dans le message news:
[EMAIL PROTECTED]
>
> 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
>
>
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: There Is No Unbreakable Crypto
Date: Wed, 18 Apr 2001 19:38:55 GMT
On 17 Apr 2001 21:16:24 GMT, [EMAIL PROTECTED] (David Wagner)
wrote, in part:
>Mok-Kong Shen wrote:
>>I continue to think, as said in another post, that this
>>means one can generate from, say, 128 random bits, a
>>secure bit string of infinite length, which seems to
>>be very counter-intuitive.
>Well, not infinite: only polynomial length, and only _if_
>you have a secure, length-doubling PRG. But yes, it's a
>marvelous, counter-intuitive, beautiful result.
And, unless a brute-force search of a 128-bit key is possible, there
doesn't seem to be anything that implausible about such a result.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Erinn Looney-Triggs" <[EMAIL PROTECTED]>
Subject: GSM Encryption and Authentication
Date: Wed, 18 Apr 2001 13:34:32 -0600
I have been trying to research the different GSM standards for encryption
and authentication and I have been able to find a lot of information
concerning A5/1 A5/2 and the authentication algorithm that was broken,
however, I am wondering about the current state of GSM protocols. I have
seen in passing a mention about A8, is this the currently used standard? Not
surprisingly the www.gsmworld.com sight is full of propoganda but not much
hard information. As well, I was wondering whether the encryption scheme is
programmed into the phone or whether it is part of the SIM? In the case of
one of the algorithms being compromised does the entire handset need to be
replaced or does it just require a upgrade to the SIM card?
Thanks,
-Erinn
------------------------------
From: "M.S. Bob" <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Wed, 18 Apr 2001 20:39:37 +0100
newbie wrote:
>
> Maybe, I'm jabbering. Because I do not have the power to express all my
> ideas in english. I'm french speaking ( + 5 others languages).
> It does not matter. The more important is to bring ideas.
> Thank you for your explanation.
Cryptographie appliqu�e
de Bruce Schneier
ISBN : 2711786765
Initiation � la cryptographie
de Gilles Dubertret
Histoire des codes secrets. De l'�gypte des pharaons � l'ordinateur
quantique
de Simon Singh
Cryptographie : Th�orie et pratique
de Douglas Stinson
"Those who do not learn from history are condemned to repeat it." --
George Santayana
You do not appear to understand some important yet basic concepts of
modern cryptography. I think most sci.crypt readers will help you to
learn more about cryptography, but it is easier, and more enjoyable
experience for everyone if you first make an effort to at least
understand "the basics" first. Find out what is already known before
making conjectures. Cryptography is a science (partly).
Please do not assume we are idiots, many ideas that people new to
cryptography have are similar to yours and have been considered before.
You can be annoying those whom are trying to help you, when you seem to
ignore their answer because you do not like the answer.
You would think me a fool to assume that I could write a prize winning
novel as my first venture into french writing. Why? Because writing,
like cryptography, is based on history and talent, one needs to be
familiar with at previous great writer's novels and one needs to
practice in order to refine one's writing. Same thing with cryptography.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.compression
Subject: Re: I took the $5000 Goldman Challenge
Date: 18 Apr 2001 19:54:09 GMT
[EMAIL PROTECTED] wrote in <9bkoag$adl$[EMAIL PROTECTED]>:
>Dale King <[EMAIL PROTECTED]> wrote:
>
>> I agree with what you meant, but your terminology and understanding of
>> information theory is a bit wrong. There really isn't such a thing as
>> random and non-random data. There are random and non-random data
>> sources.
>
>Actually, that's not true. That's the Shannon Information Theory view
>of things, but it's not the whole picture.
>
>While Kolmogorov complexity is usually mentioned here in the context
>of data compression, the original work was done to define precisely
>what is meant by "random data" (*NOT* random sources). Kolmogorov
>complexity in fact gives a very nice theory and definitions for what
>we mean by "random data" versus "non-random data"...
>
I think the problem with King is like if he was taught Eucliden
Geomtry in school. So everything is formulated towards that. THen
when he get comfronted with something more suited to Projective
Geometry he would get lost. Its hard to mix the two geometres so
I try to be of the type uses which ever one fits the problem.
One has to be flexable.
The word random is a nasty word whose meaning is very vague
many times people think of it in the Shannon sense and yet they
are using it in the K complexity sense but the fact is they are
not the same. And I think it leads to strange results.
Example supose one is using a OTP should one check to see if
the string is K complex enough. I feel most would say yes.
They may even eye the data to see if if looks random. They
may than apply the OTP to the data and then do another check
to see if it "looks" random. But if Shannon is correct should
one check at all since any sequence is as likely as any other
to be the output of a "uniformly random source". Also
if you make the set of possible OTPs smaller then when one
decrypts you are reducing the set of possible messages to
choose from. What is one really to do or make of this?
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
** 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
******************************
