A statistical evaluation of 13,000 numerical simulations of random porous structures is used to establish a correlation between permeability, porosity, tortuosity and conductance. The random structures are generated with variable porosities, and parameters such as the permeability and the tortuosity are determined directly from the structures. It is shown that the prevalent definition of tortuosity, as the ratio of length of the real flow path to the projected path in the overall flow direction, does not correlate with permeability in the general case. Also, the correlation between the conductance of the medium, as an indicator of the accessible cross section of a flow path and permeability is no more reliable than the permeability-porosity correlation. However, if the definition of tortuosity is corrected using the cross-sectional variations, the resulting parameter (i.e., the minimum-corrected tortuosity) has a reliable correlation with permeability and can be used to estimate permeability with an acceptable error for most of the simulations of the random porous structures. The feasibility of extending the conclusions from 2-dimensional to 3-dimensional configurations and the numerical percolation thresholds for random structures are also discussed.