Please enable JavaScript.

Coggle requires JavaScript to display documents.

Third Year - Coggle Diagram

- - - - Modern Take:
        Security of the system should only rely on secrecy of the keys
    - - Transposition Cipher
        Message with n characters shuffled to produce ciphertext
        N! permutations
        Example - Skytale
      - Substitution Cipher
        Switch out the characters for others using grid
        Example - Polybius
      - Caesar Cipher
        Characters shifted 3 positions forward
        Generalise the idea to K number of positions shifted
      - Monoalphabetic Cipher
        Advancement on Caesar, using a more complex substitution
        The amount a character is repeated can indicate what it represents depending on the frequency of its use in the source language, provided you know it
      - Vigernere Cipher
        Polyalphabetic, different substitutions throughout
    - - On Computers
        Represent as binary data
        XOR
        Key: stream of random bits length of message
        Encrypt bit by bit
        Use key once
      - Practicality
        Key needs to be message length
        Distributed in advance
        Once in place allows single plaintext securely sent
        Using key again fatal to security
    - - KeyStream Generator
        Takes input key K generates infinitely long stream of bits as an output, called a KeyStream
      - Properties
        Generally fast
        No error propagation
        Suitable when no buffering, when characters checked one by one
        Stateful - parties need to remain in synch
      - Main Constructions
        Based on Feedback shift registers
        Long pseudo-random keystream
        Based on pseudo-random function/permutation P and counter
        Long pseudo-random keystream
        Based on slowly evolving large secret state
        Long pseudo-random keystream
        
        LSFR-based
        Most popular
        Linear feedback shift register
        n-stage shift register
        Initial state stored in register
        State registers updated using linear feedback function
        Modify or combine to rid them of their linear properties
      - Security Issues
        XOR of plaintext can be learned from XOR of ciphertext if multiple plaintexts posses the same keystream
        Not all keystreams end up being pseudo-random, which creates vulnerabilities
        Provides no integrity, flipping a bit in the ciphertext does so in plaintext, therefore modification can remain undetected
  - - - Exhaustive Key Search
        In all attack scenarios the Plaintext - Ciphertext pairings allow for an exhaustive key search.
        Providing the plaintext is meaningful you can apply an exhaustive key-search when you posses only the ciphertext
        Should be the fastest available solution, a benchmark, to the block cipher on conception
      - Key Recovery
        Gives access to the entire cipher
        However, not required to compromise the cipher, an application that makes use of the unknown key can be utilised.
    - - IPsec Protocol
        Encrypt IP payloads +/or datagrams
        Block cipher raw encryption
        Adversary can see ciphertext
        Adversary knows plaintext - fields in IP packets fixed
        Known plaintext attack setting
        Can inject arbitrary IPsec packets with ciphertext
        ICMP error messages can contain decryptions on network
        Chosen ciphertext attack setting
      - TLS Protocol
        Encrypt application data, transport over TCP
        Using JavaScript in browser, arbitrary plaintext can be encrypted
        Adversary can see ciphertext on network
        Chosen plaintext attack setting
      - Pseudorandom
        Each key K gives a different permutation (bijection) E
        Would like each bijection from block cipher E to look like a random bijection
        Formalised to a pseudorandom property
        For concrete block ciphers - AES - we can't prove pseudorandomness
      - Cryptanalysis
        Block designer - key-dependent bijection, can't distinguish from randomly selected bijection
        Cryptanalysts look for the property of the cipher which deviates, if they can prove the cipher is non-random they have achieved a successful distinguisher attack
        This can follow-up into a key-recovery attack
        Complexity of an attack: Time, Data, Memory
        Once a exhaustive search is feasible, the cipher should be retired
    - - Ideal Block Cipher
        Each member of family E random permutation
        Not possible in practice
        Therefore aim for input-output to be computationally indistinguishable
    - - Iterative Block Ciphers
        Most Common
        Iteration of simpler key-dependent function several times
        Cryptographic strength through iteration
        Speed Vs Security - more rounds = slower
      - Round Function
        Problem generated by solution for iterative block ciphers
        Divide n-bit input string into shorter strings, apply
        especially selected transformations to substrings, and mix things
        
        Feistal
        Splits block into halves, n/2 each, builds round function w/ halves
        Example: DES
        
        SP Network
        Each round function built from substitution then permutation step
        Shannon's confusion and diffusion principles
        Example: AES
- - - - Generative Grammar
        Backus-Naur Form
    - - Automated Front End
        New front end can be reduced to a clerical exercise done by the computer
    - - Input buffering
        Source code read character by character.
        Generates source code listings and inserts error messages
        
        Character Level Lookahead
        E.G to distinguish between <= and <
        
        If the lexer reads the characters one at a time they may have to be pushed back into the input stream
      - Lexical Analyser
        (Lexer)
        Groups input characters language tokens.
        Discards formatting information.
        See CS1870
        
        Grammar
        Terminals & Non-Terminals
        Input program converted to terminals by lexer
        
        Lexemes
        Reads characters till it recognises one of these
        Put into a symbol table - token returned
        Comments + layout removed
        
        Language Design
        Decide what tokens are - represented by integers
        Attributes - compiler keeps track of actual string token represents
        
        Alphabets
        Any set of symbols
        A string in A: sequence of elements of A
        αβ: the concatenation of strings α and β
        ε: the empty string
        A∗ : the set of all strings, including ε, in A
        
        Regular Expressions
        Equivalence - two regular expressions are equivalent if they denote the same language
        Can be given names to refer to
        
        Finite state automata
        NFA - directed graph, nodes = states, connected by transitions/arrows labelled with letters.
        One start and some accepting states
        String accepted by NFA if it reaches accepting state from start
        NFAs are equivalent if they correspond to the same regular expression
        DFA - An NFA for which each state and input symbol there is one state for the machine to go to.
        DFA cannot have empty arrows/transitions
        Use finite automata to recognise whether string belongs to a regular expression - need to automatically generate DFAs
        
        Thompsons' Construction
        Mechanical method of producing NFA for Reg. Ex
        For a symbol a or ε : the start state has an arrow labelled a to an accepting state.
        For rs: join the accepting state of r to the start state of s using an ε arrow.
        For r|s: a new start state joined to the start states of r and s and a new accepting state joined to the
        original accepting states.
        For r* : ε arrows loop around the NFA for r
        
        Note
        Return to digestsSec4 - Pg 37
      - Intermediate Code Generator
        Pseudo-assembly language for an idealised machine
        Derivation trees which encode the derivation
        
        Intermediate form
        Thought of basic operations on a hypothetical machine from which machine code relatively easily generated.
        
        Three-Address Code
        Two input one output
        More amenable to automated optimisation
        x := y op z, where x,y,z are literals or identifiers corresponding to memory address.
        
        x := y op z
        Perform the operation op on the contents of addresses y and z and store the result at address x.
        
        x := y
        Assigns value of y to x
        
        x := op y
        Performs unary operation op
        
        Types of Identifier
        
        Memory Address l-values
        
        Literals r-values
        
        Program Counter
        Address pc - contains address of next instruction
        Pc increments by one after each non-go to instruction
        
        Conditional Go to
        If T is true go to L
        if T is false go to next instruction
        
        Arrays
        Provide direct access to specific index element
        Operator [] takes base address of array and off-set, returns the value in the off-set address
        Assume entries are r-values held in a single memory location
        Two machine instructions
        Assigning to arrays:
        x stored at location whose address is i off-set from the address held in A, must be an l-value.
        Two machine instructions
        
        Mini3adr
        Only has integers and arrays of integer data types
        Decelerations and assignments are C style
        Add, Sub, Multi left associative
        Boolean C style
        Indexes 0, arrays fixed
        if and while
        Semicolon delimited
        begin and end to group statements
        
        Tokens/Terminals
        Words of the same type are grouped together and have the same token
        
        Pattern
        The set of strings that correspond to a particular token
        
        Lexeme
        A string from the pattern
      - Code Improver
        Program that traverse the intermediate form and automatically rearranges the original code in this way
      - Syntax-Analyser Parsing
        Checks input fits source language
        Languages designed to be unambiguous
      - Code Generator
        Traverses intermediate form and output actual fragments of the target language
        Register allocation - most used variables added to registers
      - Loading and Linking
        Machine instructions with relocatable addresses
        Loader - places target code in to memory, gives executable target code.
        Link-editing - adding several compiled programs to form one program
      - Semantic Analyser
        Uses parser determined structure to determine input meaning
      - Passes
        Two-Pass Compiler
        Backpacking - leaving "holes"
        Lexical, syntax and semantic analysis can be done in a single pass with a parser acting as manager.
- - - - Business Case
        Determine estimated effort + time is worth expenditure
        Ongoing viability vs. business case should be monitored
        
        Typical Elements
        Problem Statement + Project Objectives
        Scope summary + alternatives/options
        Cost/Investment appraisal
        Benefits expected
        Risks
        Timescales
        Assumptions/calculations
      - Investment Appraisal
        
        CAPEX
        Capital Expenditures - funds spent for orgs benefit
        E.G A printer
        
        OPEX
        Operating Expense
        on-going operation cost for business
        E.G Salaries
        
        TCO
        Total cost of ownership - method of determining value of investment for an asset over a number of years