Archive for the ‘Uncategorized’ Category.
April 5, 2012, 5:03 am
I was trying to extract SNMP passwords from a dude data export, I couldn’t actually find them, but the dude password itself is in cleartext… here are the first steps in this process anyway:
1. Export from dude, download the file called backup*.tgz
2. Download and install sqlite3
3. Extract backup data:
3.1 Create the following C++ program, which converts the sqllite blob data to text:
#include <iostream>
#include <fstream>
#include <sstream>
using namespace std;
int main() {
ifstream file("o.txt");
for(;!file.eof();) {
string t;
getline(file,t);
if(file.eof()) break;
size_t startpos=0;
size_t endpos=0;
bool first=true;
for(size_t n=0;n<t.size();n++) {
if(t[n] == '\'') {
if(first) startpos = n+1;
else endpos = n;
first=false;
}
}
t = t.substr(startpos,endpos-startpos);
cout << "output: ";
if(t.size() > 0)
for(size_t n=0;n<(t.size()-1);n+=2) {
string s;
s += t[n];
s += t[n+1];
unsigned int c;
stringstream ss;
ss << std::hex << s;
ss >> c;
cout << string(1,c);
}
cout << endl;
}
}
[/sourcecode]
g++ fileabove.cpp #compile the above code.
The do the following to extract the strings from the blobs:
[sourcecode language="bash"]
mkdir dudebackup
cd dudebackup
cp ../backup*.tgz .
tar xvzf backup*.tgz
~/Downloads/sqlite3 ./dude.db # or wherever sqlite is...
echo '.dump' | ~/Downloads/sqlite3 dude.db > dude.txt
grep objs o > o.txt
./a.out > o.conv
o.conv will then contain a load of blob data. If you grep for “password” you’ll find the dude password. The same password seems to be used to encrypt the login credentials but I haven’t figured out where those are yet.
March 26, 2012, 9:35 pm
Another rough and ready algorithm. Finding the greatest subtree in a binary tree…
Things to remember, values in the tree can be negative so it’s not just the root (sigh).
This implementation is very inefficient. Caching sum in the node makes the efficiency reasonable I believe. But the problem is essentially recursive? Should do some googling to see if there is a better solution.
#include <iostream>
using namespace std;
class Node {
public:
Node () : left(NULL), right(NULL) {}
int value;
int sum;
Node *left;
Node *right;
int getsum() {
sum = 0;
if((left == NULL) && (right == NULL)) return value;
if(left != NULL) sum += left->getsum();
if(right != NULL) sum += right->getsum();
sum += value;
return sum;
}
};
Node *greatestsubtree(Node *current,Node *max) {
if(current == NULL) return max;
int mval = current->getsum();
if(mval > max->getsum()) max = current;
Node *l = greatestsubtree(current->left,max);
Node *r = greatestsubtree(current->right,max);
if(l->getsum() > max->getsum()) max = l;
if(r->getsum() > max->getsum()) max = r;
return max;
}
int main() {
Node *root = new Node();
root->left = new Node();
root->right = new Node();
root->value = 10;
root->left->value = -10;
root->right->value = 5;
root->left->left = new Node();
root->left->left->value = 100;
root->left->right = new Node();
root->left->right->value = 0;
root->right->left = new Node();
root->right->left->value = -8;
cout << root << endl;
cout << greatestsubtree(root,root)->getsum();
}
Version with caching…
#include <iostream>
using namespace std;
class Node {
public:
Node () : left(NULL), right(NULL),sumcache(false) {}
int value;
int sum;
bool sumcache;
Node *left;
Node *right;
int getsum() {
if(sumcache) return sum;
sum = 0;
if((left == NULL) && (right == NULL)) return value;
if(left != NULL) sum += left->getsum();
if(right != NULL) sum += right->getsum();
sum += value;
sumcache = true;
return sum;
}
};
Node *greatestsubtree(Node *current,Node *max) {
if(current == NULL) return max;
int mval = current->getsum();
if(mval > max->getsum()) max = current;
Node *l = greatestsubtree(current->left,max);
Node *r = greatestsubtree(current->right,max);
if(l->getsum() > max->getsum()) max = l;
if(r->getsum() > max->getsum()) max = r;
return max;
}
int main() {
Node *root = new Node();
root->left = new Node();
root->right = new Node();
root->value = 10;
root->left->value = -10;
root->right->value = 5;
root->left->left = new Node();
root->left->left->value = 100;
root->left->right = new Node();
root->left->right->value = 0;
root->right->left = new Node();
root->right->left->value = -8;
cout << root << endl;
cout << greatestsubtree(root,root)->getsum();
}
March 23, 2012, 11:24 pm
Some more rough and ready algorithm code, non-OO C++. Pretty bad code, not well tested, just playing.
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;
class Node {
public:
Node() {
}
vector<Node *> children;
Node *parent;
};
Node *make_random_tree(size_t size,Node *root=NULL) {
if(root == NULL) {
root = new Node();
}
Node *current = root;
size_t children=rand()%size;
for(size_t i=0;i<children;i++) {
Node *nd = new Node();
nd->parent = current;
current->children.push_back(nd);
}
for(size_t n=0;n<current->children.size();n++) {
make_random_tree(size-children,current->children[n]);
}
return root;
}
Node *get_random(Node *root,size_t avg_size) {
Node *current = root;
for(;rand()%(avg_size*2) != 0;) {
if(current->children.size() == 0) return current;
current = current->children[rand()%current->children.size()];
}
return current;
}
Node * get_next_child(Node *node,Node *child) {
bool next=false;
for(size_t n=0;n<node->children.size();n++) {
if(next==true) {
return node->children[n];
}
if(node->children[n] == child) next=true;
}
return NULL;
}
vector<Node *> get_path(Node *root,Node *n) {
vector<Node *> current_path;
current_path.push_back(root);
if(n==root) return current_path;
Node *current_child = root->children[0];
for(;;) {
current_path.push_back(current_child);
if(current_child == n) return current_path;
if(current_child->children.size() != 0) {
current_path.push_back(current_child->children[0]);
current_child = current_child->children[0];
} else {
current_child = NULL;
for(;current_child == NULL;) {
Node *old_child = current_path[current_path.size()-1];
current_path.erase(current_path.begin()+current_path.size()-1,current_path.end());
current_child = get_next_child(current_path[current_path.size()-1],old_child);
if(old_child==root) { return vector<Node *>(); }
}
}
}
// Should never get here
return vector<Node *>();
}
vector<Node *> get_path_parent(Node *root,Node *n) {
vector<Node *> v;
for(Node *current = n;current != root;current = current->parent) {
v.push_back(current);
}
v.push_back(root);
reverse(v.begin(),v.end());
return v;
}
Node *find_lca_parent(Node *root,Node *n1,Node *n2) {
vector<Node *> path1 = get_path_parent(root,n1);
vector<Node *> path2 = get_path_parent(root,n2);
for(size_t n=0;n<path1.size();n++) {cout << path1[n] << " ";} cout << endl;
for(size_t n=0;n<path2.size();n++) {cout << path2[n] << " ";} cout << endl;
size_t shortest_path_length;
if(path1.size() < path2.size()) shortest_path_length = path1.size();
else shortest_path_length = path2.size();
size_t n;
for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);
return path1[n-1];
}
Node *find_lca(Node *root,Node *n1,Node *n2) {
vector<Node *> path1 = get_path(root,n1);
vector<Node *> path2 = get_path(root,n2);
size_t shortest_path_length;
if(path1.size() < path2.size()) shortest_path_length = path1.size();
else shortest_path_length = path2.size();
size_t n;
for(n=0;(n<shortest_path_length) && (path1[n] == path2[n]);n++);
return path1[n-1];
}
int main() {
Node *root = make_random_tree(100);
Node *n1 = get_random(root,20);
Node *n2 = get_random(root,20);
Node *lca1a = find_lca_parent(root,n1,n2);
Node *lca1b = find_lca (root,n1,n2);
cout << "LCA1-a: " << lca1a << endl;
cout << "LCA1-b: " << lca1a << endl;
Node *n3 = root->children[0]->children[0]->children[0];
Node *n4 = root->children[0]->children[0]->children[1];
Node *lca2a = find_lca_parent(root,n3,n4);
Node *lca2b = find_lca (root,n3,n4);
cout << "LCA2-a: " << lca2a << endl;
cout << "LCA2-b: " << lca2b << endl;
}
March 20, 2012, 4:42 pm
This is a simple, inefficient implementation of the Burrows-Wheeler transform in C++. I wrote it just to play around with the algorithm, not for any practical application. It takes a single text file as the input, then performs the transform and reverses it:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
void bwt(string input,string &bwt_str,int &primaryidx) {
vector<string> rotations;
// 1. generate rotations of input
cout << "rotations:" << endl;
for(int n=0;n<input.size();n++) {
string s;
s += input[n];
for(int i=n+1;i!=n;i++) {
if(i==input.size()) i=0;
s += input[i];
if(i==input.size()-1) i=-1;
}
rotations.push_back(s);
cout << s << endl;
}
// 2. sort
cout << "sorted:" << endl;
sort(rotations.begin(),rotations.end());
for(size_t n=0;n<rotations.size();n++) {
cout << rotations[n] << endl;
}
bwt_str.clear();
for(size_t n=0;n<rotations.size();n++) {
bwt_str += rotations[n].substr(rotations[n].size()-1,1);
if(rotations[n] == input) {primaryidx = n;}
}
cout << "bwt string: " << bwt_str << endl;
cout << "primaryidx: " << primaryidx << endl;
}
string rbwt(string bwt_str,int primaryidx) {
vector<string> cur_str;
for(size_t n=0;n<bwt_str.size();n++) {
string s;
s = bwt_str.substr(n,1);
cur_str.push_back(s);
}
for(;cur_str[0].size() < bwt_str.size();) {
vector<string> new_str = cur_str;
sort(new_str.begin(),new_str.end());
for(size_t n=0;n<cur_str.size();n++) {
cur_str[n] = cur_str[n] + new_str[n].substr(new_str[n].size()-1,1);
}
}
cout << "reversed transform:" << endl;
for(size_t n=0;n<cur_str.size();n++) {
cout << cur_str[n] << endl;
}
sort(cur_str.begin(),cur_str.end());
cout << "Original String: " << cur_str[primaryidx] << endl;
return cur_str[primaryidx];
}
int main(int argc,char **argv) {
string s;
ifstream infile(argv[1]);
for(;!infile.eof();) {
char c = (char)infile.get();
if(!infile.eof()) s += string(1,c);
}
cout << "input: " << s << "END" << endl;
string bwt_str;
int primaryidx;
bwt(s,bwt_str,primaryidx);
rbwt(bwt_str,primaryidx);
}
RSS