Universal Turing Machine algorithm

First, I learned this based on these facts:

  1. Turing machine (TM) will be define with 7-tuple Notation, M=<Q,G,b,S,d,q0,F>.
  2. Any computation rules that can use to simulate any possible TM is called Turing-Complete.
  3. Universal TM (UTM) is TM that is Turing-Complete.

Then, the question begins:

  • If we have 7-tuple Notation of any U that is UTM, Is there an algorithm to find initial tape content P that U to simulate any TM T with any I input(s)? If it exists, Does it based on each U or pattern of U? If it does, give me some example(s)? If it does, explain the algorithm?
  • Since all possible computations can be done with TM, Is there an algorithm to make TM simulate any algorithm P written in any language? If it exists, give me some example(s)?
  • If both questions above exist the algorithm, Why don’t we just make a single UTM U and use it to program itself then do every possible computation?

Vulnerabilities in Airflow

I am by far not a security expert and I would like to use Airflow, but security is blocking the usage due to vulnerable aspects. When I asked the specifics they directed me to the given one The Airflow Celery workers deserialize pickle data that is stored in the message broker—Meaning that if I can get access to the message broker, I can achieve remote code execution inside the workers by a deserialization attack. This vulnerability was assigned CVE-2020-11982.

Originated from this blog. https://snyk.io/blog/message-brokers/

I am really getting the statement from them that Airflow is insecure. But it is the most popular, therefore there must be ways to secure it. Would there be any advise how to proceed?

Is escaping a concept in CS?

I understand "escaping data" as making an exception when matching data; for example, if a program can’t match data wrapped in single and/or double quotes without an exception, than we make an exception, "escaping" such characters to be matched.

Is escaping a concept in CS?
Is it "part of how any computer would work" or just a technical implementation in human-developed programming languages?

Minimum number of nodes to select such that every node is at most k nodes away

I received this problem on an exam a few months ago, and have kept thinking about how to solve it with no luck.

Given a binary tree where each node in the tree can either be selected or unselected, implement a function k_away() which returns the minimum number of nodes that need to be selected so that every node in the tree is at most k nodes away from a selected node.

So, the nodes simply contain a pointer to the left child, a pointer to the right child, and a boolean marking it as selected or not:

struct Node {     Node *left;     Node *right;     bool selected = false; // starts out false }; 

The problem specifies a constraint of having a time complexity of O(n) and an auxiliary space complexity of O(n).

What I’ve thought of so far:

  • It seems like there are 2^n potential solutions (if I can choose to either select or not select every node and there are 2 of them), so brute force is a bad idea
  • I’ve searched around for similar problems and the closest thing I can find is the Dominating Set problem which seems… impossible to solve at this moment in polynomial time. I doubt this problem was given as an impossible problem.
  • Running DFS to get to the leaf nodes, then counting height as recursion unrolls. Every k away, marking the node as selected. This seems to work on small test cases, but does not return the minimum number away.
  • Running BFS on the root node to find all nodes k away while using another data structure to mark all visited nodes as ‘covered’, and then recursively running the BFS on each k-away node. This also seems to work on small test cases, but again doesn’t return the minimum number away.

Are two 8 GB DDR3 (1600) better than two 8 GB DDR3 (1600) + one 4 GB DDR3 (1333)? [closed]

I have an old computer setup which has two 8 GB DDR3 (1600) RAM. I have found another 4 GB DDR3 (1333) RAM and trying to understand whether adding this 4GB RAM with those already mounted 16GB RAM will increase the computer performance or not.

I don’t have much knowledge on computer hardware. If anybody could give me an answer in layman’s term, I would be grateful.

Algorithm for summation with lowest maximum temporary sum

I’ve got this problem on my last exam, which I struggle to deal with.

Lets say we have array of N integers (it can be float too, but lets say integers for sake of simplicity. We need to sum those numbers, but we can only use operation of summing two adjacent numbers. Goal of algorithm is to sum this sequence, so maximum of sum from this operation will be lowest possible.

For example: Lets say we have array -2 5 -3. First we sum 5 and -3, so the temporary sum is 2, and our sequence changes to -2 2. Then we sum -2 and 2, so now our temporary sum is 0. As we see, maximum of temporary sums was 2, and we cant get any lower. (summing -2 and 5 would give us 3, which is higher that 2).

My goal on that exam was to find best complexity algorithm, and proof its correctness.

What i tried: First thought was to use greedy algorithm, so just sum those two numbers which give lowest temporary sum right now. Problem is, i cant neither prove it is valid way to solve it, or find any counterexample. So i write here, maybe someone finds it interesting. Thanks for your attention

Decrypting a password-protected 7z file with Delta filter fails

I have made a 7z archive using Delta filter containing a wav file and I have protected it with a password. I am running a terminal in Kali Linux. My problem is that I cannot get the password cracked using 7z2john.pl and john the ripper. If I omit the Delta compression, using only the default compression of 7z, then the cracking succeeds. My question: is it possible to use 7z2john.pl and john the ripper to crack a password-protected 7z file with Delta compression? If it is possible, how can it be done?

Here are the steps to reproduce the problem:

  1. I use the following command to create the archive:

7z a test.7z *.wav -mf=Delta:4 -peasy

I get this output:

7-Zip [64] 16.02 : Copyright (c) 1999-2016 Igor Pavlov : 2016-05-21 p7zip Version 16.02 (locale=fi_FI.utf8,Utf16=on,HugeFiles=on,64 bits,4 CPUs Intel(R) Core(TM) i5-4460  CPU @ 3.20GHz (306C3),ASM,AES-NI)  Open archive: test.7z -- Path = test.7z Type = 7z Physical Size = 1090 Headers Size = 162 Method = Delta LZMA2:15 7zAES Solid = - Blocks = 1  Scanning the drive: 1 file, 32080 bytes (32 KiB)  Updating archive: test.7z  Items to compress: 1       Files read from disk: 1 Archive size: 1090 bytes (2 KiB) Everything is Ok  
  1. I use 7z2john.pl to generate material for John the Ripper to crack the archive:

/usr/share/john/7z2john.pl test.7z > test.hash

  1. I create a word list file containing only the password I gave to the archive:

echo easy > wordlist.txt

Then I try to decrypt the file:

sudo john test.hash --wordlist=wordlist.txt

I get the following output:

Using default input encoding: UTF-8 Loaded 1 password hash (7z, 7-Zip [SHA256 256/256 AVX2 8x AES]) Cost 1 (iteration count) is 524288 for all loaded hashes Cost 2 (padding size) is 3 for all loaded hashes Cost 3 (compression type) is 2 for all loaded hashes Will run 4 OpenMP threads Press 'q' or Ctrl-C to abort, almost any other key for status Warning: Only 1 candidate left, minimum 32 needed for performance. 0g 0:00:00:00 DONE (2020-08-15 07:37) 0g/s 5.555p/s 5.555c/s 5.555C/s easy Session completed 
  1. I check if the password has been cracked: sudo john --show test.hash

I get the following output:

0 password hashes cracked, 1 left

So it seems that the decrypting did not succeed. However, I can extract the archive using command 7z e test.7z -peasy so the password should be correct. Also, if I create the archive without specifying the Delta filter using command 7z a test.7z *.wav -peasy. That way, by repeating the steps 1-4 I get the password cracked and am shown the result that the correct password has been found:

$   7z a test.7z *.wav -peasy  7-Zip [64] 16.02 : Copyright (c) 1999-2016 Igor Pavlov : 2016-05-21 p7zip Version 16.02 (locale=fi_FI.utf8,Utf16=on,HugeFiles=on,64 bits,4 CPUs Intel(R) Core(TM) i5-4460  CPU @ 3.20GHz (306C3),ASM,AES-NI)  Scanning the drive: 1 file, 32080 bytes (32 KiB)  Creating archive: test.7z  Items to compress: 1       Files read from disk: 1 Archive size: 1058 bytes (2 KiB) Everything is Ok  $   /usr/share/john/7z2john.pl test.7z > test.hash $   echo easy >> wordlist.txt $   sudo john test.hash --wordlist=wordlist.txt Using default input encoding: UTF-8 Loaded 1 password hash (7z, 7-Zip [SHA256 256/256 AVX2 8x AES]) Cost 1 (iteration count) is 524288 for all loaded hashes Cost 2 (padding size) is 11 for all loaded hashes Cost 3 (compression type) is 2 for all loaded hashes Will run 4 OpenMP threads Press 'q' or Ctrl-C to abort, almost any other key for status Warning: Only 1 candidate left, minimum 32 needed for performance. easy             (test.7z) 1g 0:00:00:00 DONE (2020-08-15 07:49) 5.263g/s 5.263p/s 5.263c/s 5.263C/s easy Use the "--show" option to display all of the cracked passwords reliably Session completed $   sudo john --show test.hash test.7z:easy  1 password hash cracked, 0 left  

Build PDA for a language with unknown input alphabet

$ L_1 ,L_2$ are regular language. We form a new language $ L_{12}$ as follows: $ L_{12}=\left \{ w_1\cdot w_2|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$

In this exersice I am not given any alphabet and I’m required to build PDA for $ L_{12}$ , but by definition $ M=\left \{Q,\sum,\Gamma ,\delta ,q_0,-|,F\right\}$ and I don’t have any alphabet to work with.By intuition if the alphabet is similiar can effect the solution than if it wasn’t similiar.

Hardening my VPN Killswitch

I am currently creating a VPN Killswitch and so far it manages to keep traffic out, I just wanted to run it by others in order to catch something I missed. The killswitch uses source and destination ports, along with source and destination IPs rather than group IDs mentioned here, as I cannot get openvpn to run AFTER the script rather than before the script. I believe this has to do with the OpenVPN assigning the GID after it establishes the connection.

My main questions along with any other error or vulnerability one may find is this:

  1. Upon execution of the script, it outputs the error: iptables: Too many links. I am assuming that has to do with lines regarding NAT
  2. I am also curious if there is a better way to implement the lines using DNS at the bottom as I recall DNS uses TCP with the queries are too large for UDP packets, I am just wondering if there is a safe way of doing that rather than allowing all traffic over port 53, unless that isn’t as bad an idea as I am thinking it is.

CODE:

#!/bin/bash  declare LAN_IP_WITH_CIDR declare VPN_IP_ADDRESS declare VPN_PORT declare VPN_PROTOCOL declare VIRTUAL_INTERFACE declare LOOPBACK_INTERFACE declare INTERFACE declare DNS_IP_ADDRESS  # Flushes all previous policies iptables -F iptables --delete-chain  # Flushes all previous policies for NAT iptables -t nat -flush iptables -t nat --delete-chain  # Sets default policy for incoming/outgoing data to drop iptables -P OUTPUT DROP iptables -P INPUT DROP iptables -P FORWARD DROP  # Sets default IPv6 policy for incoming/outgoing data to drop ip6tables -P OUTPUT DROP ip6tables -P INPUT DROP ip6tables -P FORWARD DROP  # Adds onto filter table: Input and Output through loopback is OK iptables -A INPUT -j ACCEPT -i $  LOOPBACK_INTERFACE iptables -A OUTPUT -j ACCEPT -o $  LOOPBACK_INTERFACE ip6tables -A INPUT -j ACCEPT -i $  LOOPBACK_INTERFACE ip6tables -A OUTPUT -j ACCEPT -o $  LOOPBACK_INTERFACE  # Adds onto filter table: Replies to already established connections/traffic we've already sent out is OK. iptables -A INPUT -j ACCEPT -m state --state ESTABLISH  # Adds onto filter tables: Input and Output to LAN is OK on Ethernet Interface iptables -A INPUT --src $  LAN_IP_WITH_CIDR -j ACCEPT -i $  INTERFACE iptables -A OUTPUT -d $  LAN_IP_WITH_CIDR -j ACCEPT -o $  INTERFACE  # Adds onto filter tables: Input and Output to VPN IP is OK on Ethernet Interface on VPN Port iptables -A OUTPUT -j ACCEPT -d $  VPN_IP_ADDRESS -o $  INTERFACE -p $  VPN_PROTOCOL -m $  VPN_PROTOCOL --dport $  VPN_PORT iptables -A INPUT -j ACCEPT -s $  VPN_IP_ADDRESS -i $  INTERFACE -p $  VPN_PROTOCOL -m $  VPN_PROTOCOL --sport $  VPN_PORT  # Adds onto filter tables: Input and Output to TUN/TAP devices are OK.  # OpenVPN creates the virtual interface after connecting via the above policies iptables -A INPUT -j ACCEPT -i $  VIRTUAL_INTERFACE  iptables -A OUTPUT -j ACCEPT -o $  VIRTUAL_INTERFACE  # Adds onto filter tables: Input and Output queries to DNS on port 53 to specified DNS servers are OK. iptables -A OUTPUT -j ACCEPT -d $  {DNS_IP_ADDRESS[0]} -p "udp" --dport 53 iptables -A INPUT -j ACCEPT -s $  {DNS_IP_ADDRESS[0]} -p "udp" --sport 53