Initial Proposal:
Summary: We are going to parallelize rsa encryption on images using computation on GPUs, as well as exploring optimal scheduling methods through the halide api in c++. Initially, the encryption will consist of only the application of an RSA filter, but will progress to the pre-processing of the data (as an encryption scheme needs to be stateful or randomized in order to be secure). The preprocessing will be realized by shifting of pixels/blocks before encryption or/and by hashing the messages with a random oracle. Finally, more advanced security goals could be reached. The first security improvement would be encrypting data with a symmetric stateful/randomized cipher (harder to parallelize but improve security) using the AES protocol (the RSA protocol would then be used only for both party to agree on the symmetric key). A second improvement could be adding an authentication tag using a secure MAC (for example MD5 or SHA1) to prevent active MITM attacker. The final scheme would then reach SSL standards.
Background: RSA encryption is based on modular arithmetic and discrete logs. Specifically, the security lies on the assumption the calculating the discrete log of a value is a hard problem (that can’t be achieved by an attacker in a polynomial time). Two random large prime numbers p and q are chosen to define N = pq. All further operation will be performed in the group Z_N. For example, x and y are multiplicative inverses modulo N if x * y == 1 mod N. Z_N is the space defined by all numbers in Z_N with a multiplicative inverses (all elements x respecting gcd(x, N) ==1 according to Bezout theorem). The order of Z_N* is phi = (p-1) * (q-1). RSA encryption takes advantage of this to create two keys, a public and a private key. The public key pk = (e, N) is used to encrypt data. The private key sk = (d, N) is used to decrypt, as explain below. e and d have to be multiplicative inverses in Z_N* (i.e ed = 1 mod phi). p and q are not communicated. Since the factoring problem is believed to be hard, no attacker can find p and q (therefore phi) in a polynomial time. The encryption algorithm of a message m is Finally: E(pk, m) = m^e The decryption algorithm for a cipher c is a trapdoor function: D(sk, c) = c^d Correctness : according to euler’s theorem, D(sk, (E(pk, m)) = (m^e)^d) = m^ed = m mod N (ed = phik + 1). Again, the security lies on the discrete log problem and the factoring problem, making impossible for an attacker to find the trapdoor d.
Challenges: The process of applying a filter to an image is highly parallelizable as it simply involves applying a translation to each pixel, like a convolution. The tricky part of this is optimizing the scheduling of the filter application to best make use of locality and parallelism as we want the consumer of the filtered pixels to consume as close to the application of the filter as possible in order for it to have the best possible locality. The act of shifting pixels around is more involved as it requires loads of non contiguous memory and planning of where to shift each pixel. This cannot be done concurrently and forces serialization. In order to speed up the process of applying the RSA key filter to each pixel, we plan on manipulating the ordering of tasks through the halide api for c++. This api will allow us to be able to quickly test scheduling methods in order to see which one gives us the best performance by maximizing locality and/or parallelism. In order to speed up the pixel shifting, we plan on using halide to help us test scheduling again along with testing the three methods of prefetching discussed in lecture in order to see if accesses to noncontiguous memory can be sped up when shifting occurs.
Resources: In terms of starter code, our project will mainly be started from scratch, however, the project will involve us using prewritten library code, mainly we will be using pre-existing code that allows for quick generation of random primes (p and q) in c/c++. In terms of the machine requirements, we will most likely use the gates cluster machines as we will need access primarily to GPUs (gates clusters have Nvidia gtx 1080 GPUs). Before writing code, we read a paper on the application of RSA encryption on images in parallel using cuda. That paper is cited here: Tuteja, Vaibhav. “Image Encryption Using Parallel RSA Algorithm on Cuda.” Ijcncs.org, July 2014, www.ijcncs.org/published/volume2/issue7/p3_2-7.pdf. More advanced goals: A GPU accelerated SSL proxy https://shader.kaist.edu/sslshader/
Goals and Deliverables: Plan to Achieve: We plan to write the most performance code possible for the parallel application of the RSA key filter to each pixel. Our deliverable will consist of an analysis of the different pipeline scheduling methods we tried out, stating which one was best with graphs to support our findings. Our demo will include us running encryption and decryption on an image and showing how much faster our implementation is over the best serial implementation. Hope to Achieve: We hope to also be able to write a correct parallel algorithm to complete the pixel shifting of the encrypted image in parallel utilizing the same public, private key paradigm as the shifting needs to be reversible and hard to predict. We plan on demoing this feature in the same way we will demo the parallel application of the RSA encryption filter. -Potential Performance Expected: According to the paper we used as reference for our project inspiration, the researchers involved were able to filter 800 Mpixels/sec for a filter size of 9 pixels (3x3 convolution) with cuda. We hope to exceed this and achieve 850 Mpixels/sec as halide has been shown to slightly outperform cuda as it allows for the programmer to optimize scheduling.
Platform Choice: Our platform/language choice of c/c++, cuda, and halide is the best combination for this job as our project involves fast, parallel image processing. Cuda is a language that will allow for us to dictate computation to the GPU. Halide will be especially important for this task, as it is a domain specific language optimized for image processing and effective scheduling for such tasks. This is because halide allows for the programmer to quickly and easily iterate through the scheduling space for a given problem, while allowing the programmer to parallelize and vectorise operations relative to variables. This will allow for us to find the fastest schedule that maximizes the potential locality and parallelism possible for this task. We will also use the perf counter if possible to monitor cache misses in solution.
Schedule Tentative: -Week 1: Get serial implementation started (RSA encryption) and finish reading paper on parallel RSA. -Week 2: Finish serial implementation for RSA encryption and begin to apply it to images. -Week 3: Parallelize application of RSA filter and begin optimizing that parallel solution with halide. -Week 4: finish optimizing parallel application of RSA, test incrementally to get graph data for time of execution, and begin to work on pixel shifting. -Week 5: Finish pixel shifting and begin to start testing performance of pixel shifting. Begin working on write up. -Week 6: Try to finish optimization of pixel shifting with prefetching in order to get fastest and most secure encryption implementation. This will be our final product. Finish graphs and write up on performance characteristics of each algorithm tested and what made our fastest one the best one (discuss locality and parallelism exploited).
Checkpoint Writeup as of 11/19/2018:
Schedule (Of things left to do): Week 3: -Figure out how to create make file such that halide compiles on the gates clusters, and not just locally on our machines. This is so that we are sure that our performance is the best it can be. Our laptops are not as powerful as the gates clusters. -Get halide working with images, without advanced scheduling techniques. Week 4: -Begin to fine tune scheduling (implement both inline and sliding window to see which is better), but without prefetching. (This is two tasks, inline first, then sliding window) Week 5: -Prefetch data in loops to hide memory read latency and make encryption as efficient as possible. This particular task is very important and will most likely take all week. The OAEP alg mandates that we memcpy the image chunk into a contiguous section of memory, but figuring out how to most effectively prefetch data when there is a large amount of data dependency will be tricky (kind of like traversing a linked list). Week 6: -Begin to make graphs to show speed up of different scheduling algorithms. -Test on multiple images of varying sizes to see how size affects the performance of the encryption and decryption. Will graph this as well.
Summary: So far, we have both learned halide syntax and more about how halide works to speed up computation and make finding the most efficient schedule possible in a quick manner (optimal scheduling is an np-complete problem). We have also devised our hashing algorithm as well as the encryption algorithm to securely encrypt the images. The algorithm is as follows: We will decompose the image into blocks per processing unit (in this case cuda threads scheduled by halide). Each of these blocks will be moved to a block of contiguous section of memory. After that, we apply OAEP (Optimal Asymmetric Encryption Padding) which involves taking our message and xoring it with G(r) where r is a random number and G is an instance of SHA-256. We then apply H, another instance of SHA-256, to the resulting array and then xor that with the random number. The result of the first xor is then concatenated to the front of the result of the second xor to create the hashed image. We then apply an RSA filter to each member of the resulting, hashed array (pixels) in order to encrypt the image. Decryption is a very similar process to the one above, given all necessary information is present for the decrypter. Decryption is performed by extracting the random number from the hashed components through an xor operation (in our case, this will be an array of the same random variable rather than one singular value). The original message or image chunk in our case, can be extracted through another xor operation. Additionally, we have begun to experiment with scheduling with halide and have figured out which portions of the above stated algorithm can be done in parallel and which ones can be sped up with pipe lining for better locality (either inline or sliding window scheduling).
Goals: As far as our goals are concerned, we are on schedule right now. We are finishing our makefile up so that we can compile on the ghc clusters. We have currently been running halide locally on our machines. In our project proposal, we spoke about two main goals: Parallel RSA encryption. Parallel Image rotation to improve security. As we began to write code for our checkpoint, we realized that there was a much more effective way of improving the security of our encryption without including additional data dependencies with image partition rotation (Breaking the image into pieces and rearranging them to scramble blocks of pixels). Our new method for increasing security is the OAEP algorithm described above. Our new, more attainable goal, is to achieve better security over the standard RSA encryption with a popular technique applied to text encryption (images and text are both just comprised of bytes, so the the technique can be used to encrypt both types of media as it is medium independent).
Poster: At our poster session, we plan on performing a demo. The demo will involve a live encryption and decryption of an image that will be timed. The image will be shown before the encryption, after the encryption and before the decryption, and after the decryption to compare it to the original. We will ask the audience if they can find differences between the original image and the image after the decryption. We will also ask if the audience can tell that the encrypted image and the decrypted represent the same image (Can be easy to tell with only RSA encryption without OAEP).
Issues/Concerns: Our two main concerns are: -Making sure that out inputted image is casted to a format that we can directly perform computation on, and then be able to output to file and display using X11 forwarding through the command-line. Reading in the images has been harder than expected, because we had initially planned on serializing the code and then parallelizing it in steps, however, we decided to cut out the middle parallelization that did not include halide, because halide has a routine that allows for the programmer to easily read in and manipulate images as integer arrays. We will still write the sequential solution as it will provide a good benchmark for how much better our parallel solution is to the sequential one. It is worth noting that a lot of this algorithm is data dependent, so the benchmark will allow for us to see how effective our scheduling and prefetching really were. -Using prefetching and either inline or sliding window scheduling in order to speed up the OAEP step. That step has some parallel computation (Each square can be encrypted and decrypted in parallel, and within OAEP, the xor steps can be parallelized as they are being performed on arrays and not on single integers), however, the majority of the OEAP step involves sequential computation. The only way to speed that up is to take advantage of cache locality and the ability to hide the latency of memory reads by prefetching or reading earlier by efficiently scheduling and prefetching.
Final Report (12/15/2018):
Summary: We used Halide to efficiently schedule a parallel encryption pipeline on images. We optimized for two different situations. The first being simple RSA encryption with OEAP to sign the message. The RSA component of this is to encrypt the message, and the OEAP component of this is used to ensure that the message came from the expected sender. This situation was is very data parallel and computationally driven, so there is a large amount of arithmetic intensity, but the RSA component is expensive. For that reason, we decided to parallelize by tile in order to more efficiently encrypt one image, by row, by blocks of rows, and by streaming data in order to determine which schedule would best optimize the encryption.
Background: Halide is a framework built within C++ that allows for high performance image processing and easier scheduling for complex parallel projects. In the case of Halide, the schedule is written separately from the algorithm itself. This is because the functions in Halide are treated as objects (it is more functional than imperative), and each possible schedule is an attribute of the Func class in Halide. If we had attempted to perform this encryption in parallel without the use of Halide, we would need many data structures in order to pass over the image, change each contiguous section to a string, that is then hashed. In order to ensure that we do not need to pass over the image again to reconstruct these strings for decryption, we would then have created an array of all of the strings to ensure constant time access of each string, as well as no data dependencies so each string can be accessed in parallel.
However, since our end product used Halide, the data structures we used were Halide::Buffer<unsigned char*>, Halide::Buffer<uint8_t>, Halide::Expr, and Halide::Func. These structures are all Halide specific types. In this case, Halide::Expr represent scalar types, and Halide::Func evaluate to one or more of these scalar types. Scalar types in Halide are the same primitive types that exist in C++ (uint8, uint16, float, char, etc...). The buffer types in Halide are single typed and are essentially arrays that contain the image input and output data that Halide applies the pipelines we defined over.
As discussed earlier, the encryption of images or string messages comes in two flavors, RSA and serial symmetric. In the case of RSA encryption with OAEP signing, the computation is very highly data parallel, but is very computationally expensive as RSA requires the use of an exponent, which O(logn) in the worst case. In order to speed this up, we opted to utilize the sliding window based scheduling model, which is essentially parallelizing by tile. In this case, we set the work decomposition for each thread to be a block of pixels. Each thread then sequentially will perform the RSA encryption from the Crypto++ library over each pixel in that blocked section. This is an example of sliding window based scheduling, because for each thread, the entire block is cached, encrypted, and then written back to memory. This scheduling method gives us the best locality, while also making sure that our granularity per thread is not too fine as this would result in too much scheduling overhead with scheduling multiple workers to the same execution context.
The other method of of encryption is more sequential, but is much faster as it only requires an xor operation per iteration. This operation involves breaking the image down into contiguous messages. In our case, a section of rows, and then performing hashing on that message followed by an xor with the next set of rows data. This method is much faster than RSA, but is not a data parallel problem. It is more of a bandwidth bound problem. For this reason, we attempted to optimize this problem mainly by prefetching these blocks in order to hide the memory latency of accessing them. This would have allowed us to be able to take advantage of this faster, serial alg by parallelizing over multiple images. We made each image segment a half a row, and prefetched four segments (two rows) in advance in order to ensure good performance. This methodology was later abandoned as we could not decrypt the images, and Halide does not have native prefetch instructions. It sends the data to the cpu as it performs the computation, so we could explore different prefetching strategies.
Approach: Our project requires many different translations to the image itself in order to guarantee that the encryption we are performing is actually secure. For this reason, we decided to use the Crypto++ framework. This framework has functions for fast random number generation that uses a seed and translation function rather than picking numbers based on the system clock value. Crypto++ also has a class defined to take in an input string, and an output string in order to perform RSA encryption with OAEP signing after the generation of large prime numbered public and private keys (public for encryption and private for decryption). Initially we had opted to write our own implementation of RSA encryption using a library called primeseive in order to generate fast primes, in order to make the encryption process more modular.
What we had originally intended was to use our own modular encryption to create an encryption method that would be able to work with more scheduling methods like producer consumer based or in-line based scheduling. We found that this did not work, as we were creating different forms of encryption that would then need to be tested and proven to be secure. Without this crucial step, we cannot be sure that we are encrypting any data. We also could not guarantee with our own encryption method is that no data would be lost between the decrypted image and the original.
For that reason, we opted to use the library functions present in Crypto++ in order to safely encrypt and decrypt out image chunks with a proven strategy. Mixing this library with Halide was especially difficult, because Halide is a functional framework where the user defines pipelines that take in the input at a given index in the image and perform a translation on them. This works well for scheduling these parallel algorithms in image processing, because those algorithms contain translations that are very highly data parallel, like brightening the pixels in an image, that allow for the user to create a schedule that takes advantage of the large amount of arithmetic intensity possible in these algorithms. Crypto++ on the other hand, takes in two strings as arguments, one being the input, and the other being a string sink where the encrypted message will be written to. This means that we had to predefine the input and output buffer objects to be passed into the pipeline, and figure out how to return references to the underlying value within the object in order to be able to encrypt the image bytes with this library.
Because we wanted to explore many different scheduling methods in order to best optimize our program, we opted to use Halide as it allows for the user to separate their scheduling method from their algorithm. This is because Halide was created using object oriented programming in order to create a functional language style framework within C++. This allows for the user to define a pipeline as a Halide::Func object, and then define the schedule by calling attributes on the Halie::Func object itself. These attributes include parallelize, vectorize, tile, and un_roll, which parallelize a for loop, vectorize data parallel computation using SIMD vectorization in float registers, parallelize data parallel work by block decomposition per thread, and unroll loops for better locality respectively.
In order to optimize RSA encryption for our images, we opted to use tiling to parallelize by tile. By this, we mean that the decomposition of work per worker thread is a block of pixels in the image.
Our target machine for this project was the CPUs on the shark machines, as those are the only machines where the CLANG and LLVM compilers, which we needed in order to compile Halide on the machines. The shark machines have 20 Nehalem cores, each with 2-way hyperthreading, so we had 40 cores in total to make use of. With this in mind, we partitioned our images into 40 blocked segments where each hyperthread was mapped to a block of the image, so that every block could be executed upon in parallel, due to the fact that each hyperthread has its own execution context. This hardware was perfect for the job we were doing, because of the fact that the work is very highly data parallel. A cuda GPU would have better as it would allow for us to allocate a full warp per execution context to speed up the time it would take to process each image block, because that would allow for each block to be executed on by 32 separate threads. Unfortunately however, we could not use the gates cluster machines as the binaries for the LLVM and CLANG compilers were too large for us to be able to download to the machines without exceeding our download disk quota.
We did not use all 40 hyper threads at once however, as we found that using all 40 threads created a decomposition that would result in a large amount of false sharing between threads, because two threads that were mapped to adjacent blocks would end up data on the same cache line. In order to fix this, we opted to halve the amount of execution contexts we used, and instead used only 20 of these contexts to ensure fast performance, without the creation of instances of false sharing.
The other alg that we used, utilizes a serial approach. As stated earlier, this approach is faster than RSA encryption, however, it cannot be parallelized. For this reason, we opted to use this method to parallelize multiple different images in parallel. For demo purposes, we opted to simply see how quickly we could encrypt and decrypt three different images in parallel. Given the fact that we still have 40 different execution contexts, we decided to only test the parallelizing of three images because the size of each image is large and we did not want to create any instances where false sharing could occur.
The original serial algorithm involved four nested for loops where the other two iterated over blocks and the inner two loops iterated within the block itself. This implementation had good cache locality, but made rewriting the code difficult in order to test out the different scheduling methods. After we wrote our serial algorithm, we had to make many changes to our algorithm as we parallelized it in order to make it more modular and easier to experiment with other parallel scheduling techniques. These changes involved having to rewrite all of our code from standard C++ algorithms to Halide pipelines. The actual serial algorithm itself executed the same operation to all pixels in a blockwise fashion, which made parallelizing it very easy to do, and also very effective as it inherently had a large amount of arithmetic intensity (Very dense computation and essentially no communication of this information). This alg is very data parallel (SPMD), and thus mapped very well to the 40 hyperthreads located on the shark machine CPU.
Halide and regular C++ code are very different, because Halide uses classes to define its function and value types in order for it to mimic the syntax of functional languages. For this reason, getting Halide to play nicely with other libraries like crypto++ was very difficult. In order to take full advantage of Halide, we had to define Halide::Func pipelines that took in a row and column index for the image, and performed rsa_sha_oaep encryption on that pixel with the help of crypto++ RSAES_OEAP_SHA class. This sounds very simple in practice, as the pipeline logic should resemble the following: Halide::Func Encrypt(i,j) = StringSource(input(i,j),e,output(i,j)) where input(i,j) represents the pixel at input[i][j], e represents an instance of the RSAES_OEAP_SHA_Encryptor class, and output(i,j) is the corresponding location in the output buffer.
This unfortunately is not the case with Halide, because input(i,j) and output(i,j) are not values (in our case unsigned char), but are instead Halide::Expr that evaluate to the values at the specified locations when the pipeline is realized or run. For this reason, the above pipeline does not typecheck. In order to get the code to compile, we had to write wrapper functions in that take in a Halide expression and evaluate it at the specified indices so that the code type checks and compiles. Ultimately, we were able to get this done, by using a function called HalideExtern_2, which takes in an extern “C” function, and its argument types, and allows for the user to create a C++ function and turn it into a Halide_extern that can be passed into a pipeline and execute.
The schedules that we opted to test were a sequential version using Halide, because we wanted a good baseline to test our parallel schedules on, and know that Halide has special optimizations for image processing even in the serial case. We also opted to test parallel tile or blocked sections, so each thread encrypts a blocked section of the image, parallel row sections where each thread encrypted a contiguous section of rows. This helped to improve the performance as the amount of false sharing was lessened by the fact that no thread was accessing the same cache block as another. This was an issue with the tiled implementation, as our image was a 2d array, and not a 4d array. Next, we opted to vectorize the encryption for each row by using the SIMD floating point registers. This allowed for more data to be read more data at a time so the latency of loading memory was hidden slightly as the loads loaded more data at a time. The final scheduled we opted for was the producer-consumer model. This model consisted of the producer sending the consumer pieces of the image, and the consumer encrypts/decrypts the messages as they arrive. This schedule very closely resembles sliding-window based scheduling as it loads a block of memory, processes it and then moves on. This schedule had great locality, and was the most realistic as images are large and typically would not be sent as a whole, but rather in smaller pieces and processed as they come, similar to online training in machine learning.
Results: Our project was an optimization problem as we were curious to analyze the possible speed up that we could witness by improving upon our data parallel RSA encryption model. In order to achieve this, we considered an image of size 2560 x 1443 were interested in assessing the speed up possible by different scheduling methods, so our plot consisted of a model that sought to express the relationship between scheduling method and run time.
For our experimental set up for RSA, we allowed for the user to be able to specify the input path of the file relative to the location of the makefile itself. Since we only allowed for one image to be encrypted at a time, we decided to write the resulting image out to “out/encrypted.png” or “output/decrypted.png”. We then allowed the user to specify the schedule they wanted to use as the second and last command line argument.
RSA encryption is a very computationally expensive action, but is very highly data parallel. In that case, the size of our image will not affect the results of our project. Having a larger image will obviously make our encryption take longer as there are more pixels to process, but it will not affect the results of which schedule outperforms the others. For that reason, we opted to instead test our project on a small set of images, with a variety of different schedules.
We were not able to achieve perfect speed up even though our computation was very highly data parallel, due to the fact that the RSA encryption utilizes fast logarithmic exponentiation. This means that raising x to 2,000,000,000 would normally take 2,000,0000,000 iterations of multiplications of three cycles each, will be reduced to approximately 30 operations. This makes the computation bandwidth bound. This means that the cost of loading data is larger than the cost of the actual computation itself. In addition to computing the exponent, RSA encryption also uses SHA1 to hash the data and OAEP to rearrange the bytes passed to it, These operations are performed with calls to two instances of SHA1, and xoring the result after each call. These computations also take time, which is why there is a difference between in performance between the schedules, but the benefits of parallelization and improving locality are severely hindered by the bandwidth bound issue with computing exponents. This problem is very similar to the saxpy problem from homework 1.
Ultimately, we would have liked to have been able to use a GPU instead as the very heavily data parallel encryption method would have mapped very nicely to the warps, and shared memory per warp would have hidden the cost of loading the data, which hindered the amount of speed up possible for this project.
References: https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding https://en.wikipedia.org/wiki/Exponentiation_by_squaring http://www.ijcncs.org/published/volume2/issue7/p32-7.pdf http://halide-lang.org/index.html#gettingstarted https://www.cryptopp.com/wiki/Rsa_cryptography#Encryption_Scheme.28OAEP_using_SHA.29 https://shader.kaist.edu/sslshader/ https://rosettacode.org/wiki/SHA-256#C.2B.2B https://github.com/halide/Halide